57. 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:

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].
Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Example 4:

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

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
 

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals is sorted by intervals[i][0] in ascending order.
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105

这题有点儿复杂，主要场景有点多。

我这里首先先把首位直接放入的情景考虑了。然后遍历数组，看看能否进行合并，当然这里还有一种场景，新的序列是夹在前后两个序列之间的，发现这种情况直接插入返回即可。

剩下的就是需要合并的了。我们遍历数组，找出第一个可以合并的，然后直接做合并。合并了之后，再看后续的能否和前面的间隔做合并，直到最后一个元素即可。

我之前想一次到位，直接合并中间的N个元素，后来想来想去太复杂放弃了。

class InsertInterval : public Solution {
public:
    void Exec() {
    }
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
        if (newInterval[1] < intervals[0][0]) {
            intervals.insert(intervals.begin(), newInterval);
            return intervals;
        }
        if (newInterval[0] > intervals[intervals.size() - 1][1]) {
            intervals.push_back(newInterval);
            return intervals;
        }
        vector<vector<int>> res;
        bool merged = false;
        for (int i = 0; i < intervals.size(); i++) {
            if (!merged) {
                if (newInterval[1] < intervals[i][0] ||
                    newInterval[0] > intervals[i][1]) {
                    if (i != 0 && newInterval[0] > intervals[i - 1][1] &&
                        newInterval[1] < intervals[i][0]) {
                        res.push_back(newInterval);
                        for (int j = i; j < intervals.size(); j++) {
                            res.push_back(intervals[j]);
                        }
                        return res;
                    }
                    res.push_back(intervals[i]);
                } else {
                    res.push_back(vector<int>{
                        std::min(newInterval[0], intervals[i][0]),
                        std::max(newInterval[1], intervals[i][1])});
                    merged = true;
                }
            } else {
                if (intervals[i][0] > res.back()[1]) {
                    res.push_back(intervals[i]);
                } else {
                    if (intervals[i][1] > res.back()[1]) {
                        res.back()[1] = intervals[i][1];
                    }
                }
            }
        }
        return res;
    }
};