0057. Insert Interval¶
题目信息¶
- 题号:
插入区间
- 难度:
Medium
- 主题:
数组、区间、线性扫描
- 原题:
- 重点:
从插入后重新排序合并,推导到利用有序不重叠条件完成三段扫描
题目重述¶
给定若干闭区间 intervals,它们已经按左端点升序排列,并且彼此不重叠。另给一个闭区间
newInterval。
把新区间插入原序列,合并所有重叠区间,返回仍按左端点升序排列且彼此不重叠的结果。
闭区间共享端点时也算重叠。例如 [1,4] 与 [4,6] 应合并为 [1,6]。
约束为 0 <= intervals.length <= 10^4。所有端点均在 [0,10^5] 内,每个区间的左端点不大于
右端点。
自建示例¶
输入:intervals = [[1,3],[7,9],[12,15]], newInterval = [4,13]
输出:[[1,3],[4,15]]
[1,3] 完全位于新区间左侧。新区间依次吸收 [7,9] 与 [12,15],最终扩张为
[4,15]。
输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
新区间先与 [3,5] 重叠并扩张为 [3,8],随后继续吸收 [6,7] 和与右端点接触的
[8,10]。
输入:intervals = [], newInterval = [5,6]
输出:[[5,6]]
原数组为空时,结果只包含新区间。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
std::vector<std::vector<int>> appendSortAndMerge(
std::vector<std::vector<int>> intervals,
const std::vector<int>& newInterval
) {
intervals.push_back(newInterval);
std::sort(intervals.begin(), intervals.end());
std::vector<std::vector<int>> result;
for (const auto& interval : intervals) {
if (result.empty() || interval[0] > result.back()[1]) {
result.push_back(interval);
} else {
result.back()[1] = std::max(
result.back()[1],
interval[1]
);
}
}
return result;
}
std::vector<std::vector<int>> scanThreeParts(
const std::vector<std::vector<int>>& intervals,
const std::vector<int>& newInterval
) {
std::vector<std::vector<int>> result;
result.reserve(intervals.size() + 1);
int index = 0;
int mergedStart = newInterval[0];
int mergedEnd = newInterval[1];
const int size = static_cast<int>(intervals.size());
while (index < size && intervals[index][1] < mergedStart) {
result.push_back(intervals[index]);
++index;
}
while (index < size && intervals[index][0] <= mergedEnd) {
mergedStart = std::min(
mergedStart,
intervals[index][0]
);
mergedEnd = std::max(
mergedEnd,
intervals[index][1]
);
++index;
}
result.push_back({mergedStart, mergedEnd});
while (index < size) {
result.push_back(intervals[index]);
++index;
}
return result;
}
public:
std::vector<std::vector<int>> insert(
std::vector<std::vector<int>>& intervals,
std::vector<int>& newInterval
) {
return scanThreeParts(intervals, newInterval);
}
};
题解¶
统一合并基线¶
不利用输入已经有序且互不重叠的条件时,可以先把 newInterval 追加到数组,再排序并执行普通区间合并。
appendSortAndMerge 将问题直接转化为 0056,时间复杂度为 O(n log n)。
这条路线能够保证正确,但重新排序了本来已经有序的区间。原区间之间不会互相合并,真正可能变化的只有与
newInterval 相交的一段连续区间。
三段扫描模型¶
令当前待合并区间为:
merged = [mergedStart, mergedEnd]
初始时它就是 newInterval。由于原区间按左端点升序排列且彼此不重叠,从左到右扫描时,区间必然依次落入
左侧、重叠、右侧三个连续部分。
左侧区间满足:
interval.end < mergedStart
它们与新区间之间存在严格空隙,可以直接写入结果。这里不能使用 <=,因为闭区间共享端点时仍需合并。
离开左侧部分后,只要满足:
interval.start <= mergedEnd
当前区间就与 merged 相交或接触,应更新两个端点:
mergedStart = min(mergedStart, interval.start)
mergedEnd = max(mergedEnd, interval.end)
右端点扩张后,后续区间可能继续进入重叠范围,因此这一阶段必须持续到第一个
interval.start > mergedEnd 的区间。
此时当前合并段已经完整。排序保证所有更晚区间的左端点只会更大,因此它们全部位于 merged 右侧,可以在
提交一次 merged 后原样复制。
有序三段不变量¶
扫描过程中保持以下事实:
result中已经写入的区间全部位于merged左侧,保持原有顺序且彼此不重叠;merged覆盖新区间与已经扫描到的全部重叠区间的并集;尚未扫描的区间仍按左端点升序排列。
左侧区间满足 interval.end < mergedStart,写入后不会与 merged 或更右区间重叠。重叠阶段每吸收一个
区间,只把 merged 扩张到二者并集;因为两者相交或共享端点,不会填入原覆盖范围之外的空隙。
遇到第一个 interval.start > mergedEnd 后,任意后续区间也满足同样的不等式,所以重叠阶段不会再次出现。
因此三个循环无需回退,每个原区间恰好处理一次。
最终结果由左侧原区间、一个合并段和右侧原区间组成。三部分内部都保持有序,两个连接处又存在严格空隙,结果 自然按左端点升序排列且彼此不重叠。
状态演化¶
对:
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
扫描过程为:
当前区间 |
合并前 |
动作 |
合并后 |
|---|---|---|---|
|
|
左侧,直接输出 |
|
|
|
重叠,向左扩张 |
|
|
|
被完整包含 |
|
|
|
共享端点,向右扩张 |
|
|
|
右侧,结束合并 |
|
最终结果为 [[1,2],[3,10],[12,16]]。
边界处理¶
原数组为空时,三个扫描循环都不会处理原区间,算法直接写入 newInterval。
新区间位于所有原区间之前时,左侧部分为空,先提交新区间,再复制全部右侧区间。新区间位于所有原区间之后时, 先复制全部左侧区间,再提交新区间。
新区间被某个原区间完全包含时,合并后的端点等于该原区间端点。新区间跨越多个原区间时,重叠阶段持续扩张, 直到完整吸收这段连续区间。
复杂度分析¶
scanThreeParts 对每个原区间最多访问一次,时间复杂度为 O(n)。不计返回结果,只维护索引和两个端点,
额外空间为 O(1)。
追加、排序再合并的方法时间复杂度为 O(n log n),并因按值接收参数而使用 O(n) 输入副本空间。
公开入口调用 scanThreeParts,且不修改原区间和新区间。