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