# Clean C++ Solution with Binary Search to Find the Overlapping Range

• The idea is to find the overlapping range, [low, high), with binary search, and then concatenate intervals.begin(), low), mergedInterval, and [high, intervals.end()).

Time complexity: O(logN) to find the overlapping range. O(n) to copy the intervals.

``````    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
const int NaN = numeric_limits<int>::max();
vector<Interval> result;

// Find low interval that overlaps with new interval.
// i.e. First interval whose end is greater than or equal to newInterval.start.
// e.g. Given [1,2],[3,5],[6,7],[8,10],[12,16], lower_bound([NaN,4]) returns [3,5].
Interval lowInterval(NaN, newInterval.start);
auto low = lower_bound(intervals.begin(), intervals.end(), lowInterval,
[](const Interval& l, const Interval& r){ return l.end < r.end; });
if (low == intervals.end())
{
copy(intervals.begin(), intervals.end(), back_insert_iterator<vector<Interval>>(result));
result.push_back(newInterval);
return result;
}

// Find high interval (noninclusive) that overlaps with new interval.
// i.e. First interval whose start is greater than newInterval.end.
// e.g. Given [1,2],[3,5],[6,7],[8,10],[12,16], upper_bound([9,NaN]) returns [12,16].
Interval highInterval(newInterval.end, NaN);
auto high = upper_bound(intervals.begin(), intervals.end(), highInterval,
[](const Interval& l, const Interval& r){ return l.start < r.start; });
if (high == intervals.begin())
{
result.push_back(newInterval);
copy(intervals.begin(), intervals.end(), back_insert_iterator<vector<Interval>>(result));
return result;
}

// Result is [intervals.begin(), low) U mergedInterval U [high, intervals.end()).
Interval mergedInterval(min(newInterval.start, low->start), max(newInterval.end, (high - 1)->end));
copy(intervals.begin(), low, back_insert_iterator<vector<Interval>>(result));
result.push_back(mergedInterval);
copy(high, intervals.end(), back_insert_iterator<vector<Interval>>(result));
return result;
}``````

• O(n) solution, maybe not optimized, just for reference

``````class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval t) {
vector<Interval> result;
int i=0;
for(i=0; i<intervals.size(); ++i) {
if(intervals[i].end<t.start)
result.push_back(intervals[i]);
else if(intervals[i].start > t.end){
result.push_back(t);
break;
}
else { //update t
t.start=min(t.start, intervals[i].start);
t.end=max(t.end, intervals[i].end);
}
}