# C++ code use binary search

• ``````    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
if(intervals.empty()) {
intervals.push_back(newInterval);
return intervals;
}

int first=0, piv=0, count=intervals.size(), step = 0;
while(count > 0) {  // lower bound of ends
step = count/2; piv = first + step;
if(intervals[piv].end < newInterval.start) {
first = ++piv;
count -= step + 1;
} else count = step;
}

int last = first;
count = intervals.size() - first;
while(count > 0) {  // upper bound of starts
step = count/2; piv = last + step;
if(intervals[piv].start <= newInterval.end) {
last = ++piv;
count -= step + 1;
} else count = step;
}

if(last == first)
intervals.insert(intervals.begin()+first, newInterval);
else {
intervals[first].start = min(newInterval.start, intervals[first].start);
intervals[first].end   = max(newInterval.end,   intervals[last-1].end);
intervals.erase(intervals.begin()+(first+1), intervals.begin()+last);
}

return intervals;
}``````

• Just wanted to say that your solution is the most elegant solution I have seen for this question. It's amazing that this can implicitly handle all the edge cases.

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