Insert Interval

57. 插入区间

分析

遍历并处理不重叠区间（在 newInterval 左侧）：
- 将所有结束小于 newInterval 开始的区间直接加入结果集
合并重叠区间（与 newInterval 重叠）：
- 从当前位置开始，合并所有与 newInterval 有重叠的区间。合并时更新 newInterval 的左右边界：
  - 左边界取两者最小值 l = min(l, intervals[k][0])
  - 右边界取两者最大值 r = max(r, intervals[k][1])
插入合并后的新区间：
- 将合并后的新区间 [l, r] 插入结果集。
添加剩余区间（在 newInterval 右侧）：
- 将剩下的、与 newInterval 不重叠的区间加入结果集。

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        std::vector<std::vector<int>> res;
        int k = 0, n = intervals.size();
        int l = newInterval[0], r = newInterval[1];

        // 1. 将 newInterval 左侧不重叠的区间加入结果
        while (k < n && intervals[k][1] < l) {
            res.push_back(intervals[k]);
            ++k;
        }

        // 2. 合并所有与 newInterval 重叠的区间
        if (k < n) {
            l = std::min(l, intervals[k][0]);  // 更新合并区间的左边界
            while (k < n && intervals[k][0] <= r) {
                r = std::max(r, intervals[k][1]);  // 更新合并区间的右边界
                ++k;
            }
        }
        res.push_back({l, r});  // 3. 插入合并后的区间

        // 4. 将 newInterval 右侧不重叠的区间加入结果
        while (k < n) {
            res.push_back(intervals[k]);
            ++k;
        }

        return res;
    }
};