# [C++] My binary-search solution

1. Find the range of the intervals that will be merged.
2. Merge intervals and insert the new interval.

That's all. Please see my comment in the code:

``````class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval> result;
// the range of the intervals that will be merged
int ldx = -1;                // lower bound
int rdx = intervals.size();  // upper bound
// binary search for ldx
{
int left = 0;
int right = intervals.size();
while (left < right) {
int mid = left + (right - left) / 2;
Interval interval = intervals[mid];
if (newInterval.start < interval.start) {
right = mid;
} else if (newInterval.start > interval.end) {
ldx = mid + 1;
left = mid + 1;
} else {
ldx = mid;
break;
}
}
// if newInterval.start is bigger than all intervals[i].end
if (ldx >= 0 && ldx >= intervals.size()) {
result.reserve(intervals.size() + 1);
result.insert(result.end(), intervals.begin(), intervals.end());
result.push_back(newInterval);
return result;
}
}
// binary search for rdx
{
int left = 0;
int right = intervals.size();
while (left < right) {
int mid = left + (right - left) / 2;
Interval interval = intervals[mid];
if (newInterval.end < interval.start) {
rdx = mid - 1;
right = mid;
} else if (newInterval.end > interval.end) {
left = mid + 1;
} else {
rdx = mid;
break;
}
}
// if newInterval.end is smaller than all intervals[i].start
if (rdx < 0) {
result.reserve(intervals.size() + 1);
result.push_back(newInterval);
result.insert(result.end(), intervals.begin(), intervals.end());
return result;
}
}
// merge and insert (ldx <= rdx)
if (ldx >= 0 && intervals[ldx].start < newInterval.start) {
newInterval.start = intervals[ldx].start;
}
if (rdx < intervals.size() && intervals[rdx].end > newInterval.end) {
newInterval.end = intervals[rdx].end;
}
result.reserve(intervals.size() - (rdx - ldx) + 1);
if (ldx >= 0) {
result.insert(result.end(), intervals.begin(), intervals.begin() + ldx);
}
result.push_back(newInterval);
if (rdx < intervals.size()) {
result.insert(result.end(), intervals.begin() + rdx + 1, intervals.end());
}
return result;
}
};``````

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