区间操作题目实战

57.插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

• 示例 1：
  输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
  输出：[[1,5],[6,9]]
  解析：新区间 [2,5] 与 [1,3] 重叠，合并后为 [1,5]，与 [6,9] 无重叠，直接拼接。

• 示例 2：
  输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
  输出：[[1,2],[3,10],[12,16]]
  解析：新区间 [4,8] 与 [3,5]、[6,7]、[8,10] 均重叠，合并后为 [3,10]。

解题思路

由于原区间列表已按起始端点排序且无重叠，我们无需对整个列表重新排序，只需通过一次遍历即可完成插入与合并。核心思路如下：

1. 遍历原区间：逐个处理 intervals 中的区间，判断其与 newInterval 的关系。
2. 处理重叠区间：若当前区间与 newInterval 重叠，则合并两者（更新 newInterval 的起止点为合并后的范围）。
3. 处理非重叠区间：
   • 若当前区间在 newInterval 左侧（当前区间的结束 < newInterval 的开始），直接加入结果列表。
   • 若当前区间在 newInterval 右侧（当前区间的开始 > newInterval 的结束），先将 newInterval 加入结果列表，再将当前区间设为新的 newInterval（后续可能与更右侧区间重叠）。
4. 收尾：遍历结束后，将最终的 newInterval 加入结果列表。

class Solution {
public:
    // 判断两个区间是否重叠
    bool isOverlap(vector<int> &interval1, vector<int> &interval2) {
        return interval1[1] >= interval2[0] && interval2[1] >= interval1[0];
    }
    
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval) {
        int n = intervals.size();
        vector<vector<int>> ans;  // 存储结果的新数组
        
        for (int i = 0; i < n; i++) {
            auto p = intervals[i];  // 当前遍历的区间
            
            if (isOverlap(p, newInterval)) {
                // 若重叠，合并区间：更新newInterval的起止点
                newInterval[0] = min(newInterval[0], p[0]);  // 合并后的起始为两者最小
                newInterval[1] = max(newInterval[1], p[1]);  // 合并后的结束为两者最大
            } else {
                if (p[1] < newInterval[0]) {
                    // 当前区间在newInterval左侧，直接加入结果
                    ans.push_back(p);
                } else {
                    // 当前区间在newInterval右侧，先加入newInterval，再更新newInterval为当前区间
                    ans.push_back(newInterval);
                    newInterval = p;
                }
            }
        }
        
        // 遍历结束后，加入最终的newInterval
        ans.push_back(newInterval);
        
        return ans;
    }
};

关键函数解析

1. isOverlap 函数：
   判断两个区间是否重叠的核心逻辑是：区间 1 的结束 ≥ 区间 2 的开始，且区间 2 的结束 ≥ 区间 1 的开始。
   例如：[1,3] 与 [2,5] 中，3 ≥ 2 且 5 ≥ 1，故重叠；[1,2] 与 [3,4] 中，2 < 3，故不重叠。

2. insert 函数核心逻辑：

   • 遍历过程中，newInterval 始终代表 “当前待插入的区间”（可能是原始新区间，也可能是合并后的区间）。
   • 对于非重叠的右侧区间，通过 “先加入 newInterval 再更新 newInterval” 的操作，保证了结果列表的有序性（因原区间已排序，右侧区间的起始一定大于当前 newInterval 的起始）。