题目描述

给出一列互不相交的区间，现在要输入一个新区间（如果区间发生重叠，需要进行合并操作）。
初始区间已经按左端点从小到大排好序。

样例1

输入：初始区间集合 = [[1, 3], [6, 9]], 新区间 = [2, 5]
输出：[[1, 5], [6, 9]]

样例2

输入：初始区间集合 = [[1,2],[3,5],[6,7],[8,10],[12,16]], 新区间 = [4, 8]
输出：[[1,2],[3,10],[12,16]]
解释：新区间 [4, 8] 与 [3,5],[6,7],[8,10] 有重叠，所以要将它们合并。

算法

(区间合并) $O(n)$

对于新区间左边和右边的、与新区间没有重叠的区间，直接将它们按顺序插入；
对于与新区间相交的区间，我们维护合并后区间的左端点和右端点，最后再将合并后的区间插入适当的位置。

时间复杂度分析：每个区间只会遍历一次，所以总时间复杂度是 $O(n)$.

C++ 代码

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        bool has_in = false;
        for (auto interval : intervals)
        {
            if (interval.start > newInterval.end)
            {
                if (!has_in)
                {
                    res.push_back(newInterval);
                    has_in = true;
                }
                res.push_back(interval);
            }
            else if (interval.end < newInterval.start)
            {
                res.push_back(interval);
            }
            else
            {
                newInterval.start = min(newInterval.start, interval.start);
                newInterval.end = max(newInterval.end, interval.end);
            }
        }
        if (!has_in) res.push_back(newInterval);
        return res;
    }
};