# C++ 16ms simple solution

• ``````    class Solution {
public:
// oh sorry , it`s not lower_bound. it find the maximum point whose start <= newInterval.end
int lower_bound(vector<Interval>& intervals, Interval newInterval){
int left = 0, right = intervals.size() - 1;
int ans = left;
while(left <= right){
int mid = left + (right -left) / 2;
if(newInterval.end >= intervals[mid].start){
ans = mid;
left = mid + 1;

}else{
right = mid - 1;
}
}
return ans;
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
if(intervals.empty()){
return vector<Interval>{newInterval};
}else if(intervals[0].start > newInterval.end){
vector<Interval> ans(intervals);
ans.insert(ans.begin(), newInterval);
return ans;
}else if(intervals[intervals.size() - 1].end < newInterval.start){
vector<Interval> ans(intervals);
ans.insert(ans.end(), newInterval);
return ans;
}
vector<Interval> ans;
int right = lower_bound(intervals, newInterval);
int left = 0;
while(intervals[left].end < newInterval.start){
ans.push_back(intervals[left++]);
}
Interval tmp;
tmp.start = newInterval.start < intervals[left].start ? newInterval.start : intervals[left].start;
tmp.end = newInterval.end > intervals[right].end ? newInterval.end : intervals[right].end;
ans.push_back(tmp);
for(int i = right + 1;i < intervals.size(); ++i){
ans.push_back(intervals[i]);
}
return ans;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.