0056. Merge Intervals
=====================
题目信息
--------
:题号: 0056. 合并区间
:难度: Medium
:主题: 数组、排序、区间、贪心
:原题: `LeetCode 0056 `_
:重点: 从无序区间的反复比较,推导到按左端点排序后只维护当前覆盖段
题目重述
--------
给定若干闭区间 ``intervals[i] = [start_i, end_i]``,合并所有存在重叠的区间,返回若干彼此不重叠的
闭区间,并且它们覆盖的点集与原输入完全相同。
闭区间共享端点时交集非空,因此 ``[1,4]`` 与 ``[4,6]`` 也必须合并为 ``[1,6]``。返回顺序不限。
约束为 ``1 <= intervals.length <= 10^4``,每个区间满足
``0 <= start_i <= end_i <= 10^4``。
自建示例
--------
普通重叠:
.. code-block:: text
输入:intervals = [[2,4],[3,7],[9,12],[11,15]]
输出:[[2,7],[9,15]]
前两个区间合并为 ``[2,7]``,后两个区间合并为 ``[9,15]``。
端点相接与传递重叠:
.. code-block:: text
输入:intervals = [[1,4],[4,5],[5,8],[10,12]]
输出:[[1,8],[10,12]]
前三个区间通过共享端点形成连续覆盖链,最终属于同一结果区间。
包含关系:
.. code-block:: text
输入:intervals = [[1,10],[2,3],[4,7]]
输出:[[1,10]]
后两个区间完全包含在第一个区间内,不会扩大最终覆盖范围。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool overlaps(
const std::vector& first,
const std::vector& second
) {
return first[0] <= second[1] && second[0] <= first[1];
}
std::vector> repeatedlyMergePairs(
std::vector> intervals
) {
bool merged = true;
while (merged) {
merged = false;
for (int i = 0; i < static_cast(intervals.size()); ++i) {
for (int j = i + 1; j < static_cast(intervals.size()); ++j) {
if (!overlaps(intervals[i], intervals[j])) {
continue;
}
intervals[i][0] = std::min(
intervals[i][0],
intervals[j][0]
);
intervals[i][1] = std::max(
intervals[i][1],
intervals[j][1]
);
intervals.erase(intervals.begin() + j);
merged = true;
break;
}
if (merged) {
break;
}
}
}
return intervals;
}
std::vector> sortAndMerge(
std::vector>& intervals
) {
std::sort(
intervals.begin(),
intervals.end(),
[](const std::vector& first, const std::vector& second) {
if (first[0] != second[0]) {
return first[0] < second[0];
}
return first[1] < second[1];
}
);
std::vector> result;
result.push_back(intervals[0]);
for (int i = 1; i < static_cast(intervals.size()); ++i) {
const int nextStart = intervals[i][0];
const int nextEnd = intervals[i][1];
std::vector& current = result.back();
if (nextStart > current[1]) {
result.push_back(intervals[i]);
} else {
current[1] = std::max(current[1], nextEnd);
}
}
return result;
}
public:
std::vector> merge(
std::vector>& intervals
) {
return sortAndMerge(intervals);
}
};
题解
----
无序两两合并基线
~~~~~~~~~~~~~~~~
两个闭区间 ``[a,b]`` 与 ``[c,d]`` 重叠,当且仅当:
.. code-block:: text
a <= d 且 c <= b
重叠后,它们的并集仍是一个闭区间:
.. code-block:: text
[min(a,c), max(b,d)]
``repeatedlyMergePairs`` 在无序列表中寻找任意重叠对,合并后删除其中一个区间,再从头继续检查。
这种方法直接遵守定义,最终没有任何重叠对时,剩余区间就是答案。
一次扫描不能完成无序合并,因为区间扩张后可能产生新的重叠关系。例如 ``[1,4]`` 与 ``[4,5]`` 合并为
``[1,5]`` 后,又会与 ``[5,8]`` 重叠。此前已经比较过的区间因此可能需要重新检查。
列表最多执行 ``n - 1`` 次合并,每轮可能检查 ``O(n²)`` 对区间,删除元素还会移动后续内容,最坏时间可达
``O(n³)``。继续优化的关键是建立一种顺序,使已经完成的区间能够永久提交。
排序建立单向依赖
~~~~~~~~~~~~~~~~
按左端点升序排列后,后续区间的左端点不会变小。设当前尚未提交的覆盖段为:
.. code-block:: text
current = [currentStart, currentEnd]
下一个区间为 ``[nextStart, nextEnd]``。由于已经排序,必有:
.. code-block:: text
currentStart <= nextStart
于是只需比较 ``nextStart`` 与 ``currentEnd``。
若 ``nextStart <= currentEnd``,两个闭区间重叠或共享端点。合并后的左端点仍为 ``currentStart``,只需更新:
.. code-block:: text
currentEnd = max(currentEnd, nextEnd)
若 ``nextStart > currentEnd``,当前段与新区间之间存在空隙。所有更晚区间的左端点都不小于
``nextStart``,因此也一定大于 ``currentEnd``。当前段不可能再与后续区间重叠,可以永久保留,并以新区间开始
下一段。
有序覆盖段不变量
~~~~~~~~~~~~~~~~
扫描第 ``i`` 个区间前,``result`` 保持以下状态:
* ``result`` 中的区间按左端点有序;
* 除最后一个区间外,其余区间已经永久完成,彼此严格分离;
* ``result.back()`` 是所有已扫描区间中最右侧、仍可能继续扩张的覆盖段;
* ``result`` 覆盖的点集恰好等于已经扫描区间的并集。
处理新区间时只有两种转移。
重叠时,把当前段右端点扩张到两者右端点的最大值。两区间之间没有空隙,因此新区间覆盖的点集恰好等于二者
并集,不会丢失原有点,也不会填入额外空隙。不变量继续成立。
分离时,排序已经证明当前段不可能再被后续区间扩张,所以直接追加新区间。此前的最后一段转为永久完成段,
新区间成为新的活动覆盖段,不变量同样成立。
所有输入区间恰好处理一次。扫描结束时,最后一个活动段也自然成为最终段,因此结果覆盖范围与原输入完全相同,
且任意相邻结果区间都满足前一个右端点小于后一个左端点。
传递重叠
~~~~~~~~
对 ``[[1,4],[4,5],[5,8]]``,排序后顺序不变:
.. list-table::
:header-rows: 1
* - 新区间
- 当前覆盖段
- 转移后
* - ``[1,4]``
- 无
- 建立 ``[1,4]``
* - ``[4,5]``
- ``[1,4]``
- 扩张为 ``[1,5]``
* - ``[5,8]``
- ``[1,5]``
- 扩张为 ``[1,8]``
每次比较的是新区间与已经吸收前面所有重叠区间的当前覆盖段,因此由多个区间连接形成的重叠链不会遗漏。
包含区间也无需特殊处理;若 ``nextEnd <= currentEnd``,取最大值后当前段保持不变。
结果数组复用
~~~~~~~~~~~~
代码直接让 ``result.back()`` 表示活动覆盖段。重叠时修改它的右端点,分离时追加新区间,因此不需要额外维护
``currentStart`` 和 ``currentEnd``。
活动段之前的结果已经由排序证明不会再与任何后续区间重叠,所以只有最后一个区间可能变化。这正好对应有序覆盖段
不变量。
复杂度分析
~~~~~~~~~~
设区间数量为 ``n``。
无序反复合并最坏需要 ``O(n³)`` 时间,并在删除元素时产生额外移动成本。
主方法排序需要 ``O(n log n)`` 时间,随后线性扫描全部区间,耗时 ``O(n)``,总时间为 ``O(n log n)``。
主方法直接排序输入数组。不计返回结果,``std::sort`` 通常使用 ``O(log n)`` 调用栈;扫描阶段使用
``O(1)`` 额外空间。