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 <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 105
- intervals 根据 starti 按 升序 排列
- newInterval.length == 2
- 0 <= start <= end <= 105
题解
- 核心思想：可以利用贪心算法来完成该题，分为三个阶段：
- 处理新区间之前的所有区间：
将所有在新区间之前且不与新区间重叠的区间直接加入结果列表。
这一步利用了区间列表的有序性，通过比较当前区间的结束点和新区间的起始点来判断是否重叠。 - 合并与新区间重叠的区间：
遍历区间列表，找到所有与新区间有重叠的区间，并将它们合并为一个更大的区间。
合并操作通过更新新区间的起始点和结束点来实现，具体是取最小的起始点和最大的结束点。 - 处理新区间之后的所有区间：
将所有在新区间之后的区间直接加入结果列表。
这一步同样利用了区间列表的有序性，确保这些区间不会与已合并的新区间重叠。
- 处理新区间之前的所有区间：
- 复杂度：时间复杂度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;
}