# Fastest (but too complicated) C++ solution, need someone to simplify it!

• I cannot find an optimal C++ solution here so far, in my opinion, the optimal solution should have the following properties:

1. do in-place merge/insert/erase..., use the input `intervals` as final result instead of creating a new `vector<Interval>`
2. use binary search to find the start location for merging intervals

I think my solution satisfies all those requirements, but the problem is it's too long and not clean enough, I don't think it's easy to finish it in a short interview. So really needs someone to simplify it or make it more efficient if possible.
BTW, I don't think the given function interface is optimal, it returns a `vector<Interval>`, which means it will create a new `vector<Interval>` for return anyway, it should request people to modify `intervals` in place.

``````class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
// Given a set of sorted non-overlapping (guaranteed) intervals
// first deal empty case
if (intervals.size()==0) {
intervals.emplace_back(newInterval);
return intervals;
}

int idx = binarySearch(intervals, newInterval); // need to handle single-element case
if (idx==-1) {
if (newInterval.end < intervals[0].start) { // non-overlapping
pureInsert(intervals, newInterval, 0);
return intervals;
} else { // overlapping
intervals[0] = Interval(newInterval.start, max(newInterval.end, intervals[0].end));
mergeIntervals(intervals, 0);
return intervals;
}
}
if (idx==intervals.size()-1) {
if (intervals[intervals.size()-1].end < newInterval.start) { // non-overlapping
intervals.emplace_back(newInterval);
return intervals;
} else { // overlapping
intervals[intervals.size()-1].end = max(intervals[intervals.size()-1].end, newInterval.end);
return intervals;
}
}
// not boundary cases, valid idx, idx+1
if (intervals[idx].end < newInterval.start && newInterval.end < intervals[idx+1].start) { // non-overlapping
pureInsert(intervals, newInterval, idx+1);
return intervals;
} else if (intervals[idx].end >= newInterval.start) { // overlapping case#1
intervals[idx] = Interval(intervals[idx].start, max(intervals[idx].end, newInterval.end));
mergeIntervals(intervals, idx);
return intervals;
} else { // overlapping case#2: intervals[idx].end < newInterval.start, newInterval.end >= intervals[idx+1].start
intervals[idx+1] = Interval(newInterval.start, max(intervals[idx+1].end, newInterval.end));
mergeIntervals(intervals, idx+1); // should not touch intervals[idx]
return intervals;
}
}
private:
int binarySearch(vector<Interval>& intervals, Interval newInterval) { // last "<=" element
if (intervals[0].start > newInterval.start) return -1;
if (intervals[intervals.size()-1].start <= newInterval.start) return intervals.size()-1;
// the above covered single-ele case, and won't go below
// now size>=2, guaranteed 2 ends
int idxL=0, idxH=intervals.size()-1, mid;
while (1) {
mid = idxL + (idxH-idxL)/2;
if (mid == idxL) return idxL; // finally for all cases
if (intervals[mid].start <= newInterval.start) idxL = mid;
else idxH = mid;
}
// won't reach here
return -1;
}
void pureInsert(vector<Interval>& intervals, Interval newInterval, int idx) {
intervals.emplace_back(newInterval);
Interval tmp;
for (int i=idx; i<intervals.size(); i++) { // it includes final one self-swapping, it's a don't case
swap(intervals[i], intervals.back(), tmp);
}
}
void mergeIntervals(vector<Interval>& intervals, int idx) { // merge intervals if needed start from idx
// in-place merge, move forwards in vector, then pop_back
int curIdx = idx; // current merging idx
for (int i=idx+1; i<intervals.size(); i++) { // starts are sorted
if (intervals[curIdx].end >= intervals[i].start) { // merge in
intervals[curIdx].end = max(intervals[curIdx].end, intervals[i].end);
} else { // move forwards
intervals[curIdx+1] = intervals[i];
curIdx++; // update working idx
}
}
// pop_back until size == curIdx+1 i.e., [0,...,curIdx]
while (intervals.size() > curIdx+1) intervals.pop_back();
// test this function alone okay
}
template <typename T>
void swap(T& a, T& b, T& tmp) {
tmp = a;
a = b;
b = tmp;
}
};

``````

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