leetcode 面试经典 150 题：插入区间

链接	插入区间
题型	数组（区间）
题序号	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：
输入：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] 重叠。

提示：

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= starti <= endi <= 10⁵
intervals 根据 starti 按升序排列
newInterval.length == 2
0 <= start <= end <= 10⁵

题解

核心思想：可以利用贪心算法来完成该题，分为三个阶段：
- 处理新区间之前的所有区间：
  将所有在新区间之前且不与新区间重叠的区间直接加入结果列表。
  这一步利用了区间列表的有序性，通过比较当前区间的结束点和新区间的起始点来判断是否重叠。
- 合并与新区间重叠的区间：
  遍历区间列表，找到所有与新区间有重叠的区间，并将它们合并为一个更大的区间。
  合并操作通过更新新区间的起始点和结束点来实现，具体是取最小的起始点和最大的结束点。
- 处理新区间之后的所有区间：
  将所有在新区间之后的区间直接加入结果列表。
  这一步同样利用了区间列表的有序性，确保这些区间不会与已合并的新区间重叠。
复杂度：时间复杂度O(n)，通过一次遍历完成所有操作，每个区间最多被处理一次。空间复杂度O(n)
主要由结果存储 result 决定，其大小与输入区间列表的长度成正比。
c++ 实现算法：

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> result;  // 用于存储结果int i = 0, n = intervals.size();// 1. 将所有在 newInterval 之前的区间加入结果// 遍历 intervals 的每个区间，如果当前区间的结束位置 (intervals[i][1]) 小于 newInterval // 的起始位置 (newInterval[0])，说明当前区间完全位于 newInterval 的左侧。while (i < n && intervals[i][1] < newInterval[0]) {result.push_back(intervals[i]);i++;}// 2. 合并与 newInterval 重叠的区间//当前区间的起始位置 (intervals[i][0]) 小于等于 newInterval 的//结束位置 (newInterval[1])，说明它们存在重叠。while (i < n && intervals[i][0] <= newInterval[1]) {newInterval[0] = min(newInterval[0], intervals[i][0]);newInterval[1] = max(newInterval[1], intervals[i][1]);i++;}//将合并后的区间放到 result 中result.push_back(newInterval);// 3. 将剩余的区间加入结果while (i < n) {result.push_back(intervals[i]);i++;}return result;
}

算法推演：

输入： intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
newInterval = {4, 8};

步骤 1：处理在 newInterval 之前的区间
遍历 intervals，直到遇到与 newInterval 重叠的区间为止。
区间{1, 2} 在 newInterval 之前，直接加入 result：
result = {{1, 2}}

步骤 2：合并重叠区间
区间 {3, 5} 与 {4, 8} 重叠，合并后 newInterval 更新为 {3, 8}。
区间 {6,7} 与 {3, 8} 重叠，合并后 newInterval 更新为 {3, 8}。
区间 {8, 10} 与 {3, 8} 重叠，合并后newInterval 更新为 {3, 10}。
将合并后的区间 {3, 10} 加入 result：
result = {{1, 2},{3, 10}}

步骤 3：处理剩余区间剩余区间 {12, 16} 没有与 newInterval 重叠，直接加入 result：
result = {{1, 2}, {3, 10}, {12, 16}}

输出： [[1, 2], [3, 10], [12, 16]]

c++ 完整demo：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> result;  // 用于存储结果int i = 0, n = intervals.size();// 1. 将所有在 newInterval 之前的区间加入结果// 遍历 intervals 的每个区间，如果当前区间的结束位置 (intervals[i][1]) 小于 newInterval // 的起始位置 (newInterval[0])，说明当前区间完全位于 newInterval 的左侧。while (i < n && intervals[i][1] < newInterval[0]) {result.push_back(intervals[i]);i++;}// 2. 合并与 newInterval 重叠的区间//当前区间的起始位置 (intervals[i][0]) 小于等于 newInterval 的//结束位置 (newInterval[1])，说明它们存在重叠。while (i < n && intervals[i][0] <= newInterval[1]) {newInterval[0] = min(newInterval[0], intervals[i][0]);newInterval[1] = max(newInterval[1], intervals[i][1]);i++;}//将合并后的区间放到 result 中result.push_back(newInterval);// 3. 将剩余的区间加入结果while (i < n) {result.push_back(intervals[i]);i++;}return result;
}int main() {vector<vector<int>> intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};vector<int> newInterval = {4, 8};vector<vector<int>> result = insert(intervals, newInterval);for (const auto& interval : result) {cout << "[" << interval[0] << "," << interval[1] << "] ";}return 0;
}