Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution: Using sorting

This solution is quite similar to merge overlapping intervals.

1. Insert the new interval to the sorted intervals
2. Sort the intervals vector
3. Start merging overlapping intervals

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
    vector<Interval> res;
    int n = intervals.size(), cur = 0;

    while (cur < n && intervals[cur].end < newInterval.start) {
        res.push_back(intervals[cur++]);
    }
    while (cur < n && intervals[cur].start <= newInterval.end) {
        newInterval.start = min(newInterval.start, intervals[cur].start);
        newInterval.end = max(newInterval.end, intervals[cur].end);
        ++cur;
    }

    res.push_back(newInterval);
    while (cur < n) {
        res.push_back(intervals[cur++]);
    }
    return res;
}