题目描述

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

模拟 $O(n)$

如果 interval i 与 new interval 没有overlap:
如果在new interval之前，直接加入res中
如果在new interval之后，将new interval加入res，再加入interval i

如果 有 overlap，如果还没有merge过，merge后加入res，否则与res最后一个interval merge
最后 i 都遍历完了，如果还没有merge，直接将 new interval 放入 res

C++ 代码

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if(n==0) return vector<vector<int>> {newInterval};

        vector<vector<int>> res;
        bool merged = false;
        for(int i=0; i<n; i++) {

            if( intervals[i][1] < newInterval[0]) {
                // 在new interval之前的 non overlap interval
                res.push_back(intervals[i]);
            } else if(intervals[i][0] > newInterval[1]) {
                // 在new interval之后的 non overlap interval
                if(!merged) { 
                    res.push_back(newInterval);
                    merged = true;
                }
                res.push_back(intervals[i]);
            } else { // 有overlap
                if(merged) { // new interval 已经merge到 res 的最后一个
                    res.back()[1] = max( res.back()[1], intervals[i][1]);
                } else { // new interval 还没有merge
                    res.push_back( { 
                        min(intervals[i][0], newInterval[0]), 
                        max(intervals[i][1], newInterval[1]) });
                    merged = true;
                }
            }
        }

        // 注意 new interval 可能在所有的 interval 之后
        if(!merged) { res.push_back(newInterval); } 

        return res;
    }