LeetCode LCR 074. 合并区间
目录
题目描述
题意分析
给一组闭区间，把所有有重叠的区间合并掉，返回一个互不重叠、恰好覆盖原输入所有点的区间集合。
「闭区间」这个前提决定了相接算不算重叠：
[1, 4]与[4, 5]共享端点 4，在闭区间语义下它们是连通的，必须合并成[1, 5]。判定式里那个等号的取舍完全由这一点决定。输入没有任何顺序保证，区间可以任意交错、包含、相离。而「合并」这件事本质上是在处理相邻关系——只有位置上挨着的区间才可能重叠——所以输入的无序性正是首要障碍。
约束里区间数可达 $10^4$，端点值可达 $10^4$。规模允许 $O(n \log n)$ 的排序，但不允许 $O(n^2)$ 的两两比较合并（那是 $10^8$ 次并且还要反复迭代直到稳定）。
边界上要注意：只有一个区间时直接返回它；完全包含的情况（
[1, 10]与[3, 5]）合并后右端点不能被缩小；退化区间（[5, 5]）是合法输入；最后一个正在维护的区间必须记得写进答案。
解法：排序后扫描
核心思路
暴力做法是反复扫描区间集合，找到任意一对重叠的就合并成一个，直到某轮扫描下来一次合并都没发生。正确但代价高昂：单轮就是 $O(n^2)$ 的两两比较，而且可能需要多轮才收敛。
瓶颈在于「任意一对」的搜索完全没有方向感。合并是有传递性的（
A与B重叠、B与C重叠，三者就该并成一个），暴力做法却在无序集合里盲目地找配对，同一段关系被反复检查。观察的切入点是：如果所有区间按左端点升序排好，那么重叠一定只发生在相邻位置之间。理由是——扫描到某个区间时，前面已处理的区间左端点都不比它大；只要它的左端点没有超过「当前已合并段的右端点」，就必然与之相交；一旦超过，那么它后面的所有区间左端点更大，也一定不会再与前面这段相交。于是「找重叠」从全局搜索降级成一次线性扫描。
由此定下扫描时维护的状态：
(st, ed)表示当前正在生长的合并段，初值取排序后第一个区间。每读入一个新区间(s, e)：若ed < s，说明新区间与当前段完全分离（注意ed == s时闭区间仍相接，不算分离），就把当前段封存进答案并用新区间开启下一段；否则两者相交，把当前段的右端点扩张为max(ed, e)。用
max而不是直接赋值为e，是因为存在包含关系：[1, 10]后面跟[3, 5]时，新区间的右端点更小，直接赋值会把已经覆盖到的 10 缩回 5。维持的不变量是：扫描到位置
i时，答案数组里的区间全部已经最终确定、互不重叠且都在st左侧；(st, ed)是与intervals[i..]可能还有交集的唯一一段。循环结束后把最后这一段补进答案，就得到完整结果。
解题步骤
- 先按左端点升序排序。这是整个算法成立的前提——只有有序才能保证「不相交就永远不再相交」，也才能把重叠判断局部化到相邻两项。
- 用排序后的第一个区间初始化
st与ed，作为第一段的起点。题目保证至少有一个区间，所以直接取下标 0 是安全的。- 从第二个区间开始遍历，每次取出
(s, e)与当前段比较。只与「当前段」比较而不与答案里的历史区间比较，是因为历史区间都已被证明不会再与后续区间相交。- 判定分离用
ed < s（严格小于）。写成ed <= s会把相接的[1, 4]与[4, 5]当成两段，与闭区间语义矛盾。- 分离时先把
(st, ed)追加进答案，再把st、ed重置为新区间的两端。顺序不能颠倒，否则当前段会丢失。- 相交时只更新右端点为
max(ed, e)，左端点st保持不变——排序保证了st已经是这一段中最小的左端点。- 循环结束后，把最后维护的
(st, ed)追加进答案。这一步极易遗漏：最后一段永远不会经由「分离」分支被写入。以
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]走一遍：按左端点排序后顺序不变。初始化st = 1、ed = 3，答案为空。读入[2, 6]：ed = 3不小于s = 2，说明相交，右端点扩张为max(3, 6) = 6，当前段变成(1, 6)。读入[8, 10]：ed = 6 < 8，分离，把(1, 6)写进答案，当前段重置为(8, 10)。读入[15, 18]：ed = 10 < 15，分离，把(8, 10)写进答案，当前段重置为(15, 18)。循环结束，把最后的(15, 18)补进答案。最终返回[[1, 6], [8, 10], [15, 18]]。若在此基础上再追加一个[16, 17]，读到它时ed = 18不小于 16，判定相交，右端点取max(18, 17) = 18保持不变——这正是max存在的意义。
代码实现
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int st = intervals[0][0], ed = intervals[0][1];
List<int[]> answer = new ArrayList<>();
for (int i = 1; i < intervals.length; ++i) {
int s = intervals[i][0], e = intervals[i][1];
if (ed < s) {
answer.add(new int[] {st, ed});
st = s;
ed = e;
} else {
ed = Math.max(ed, e);
}
}
answer.add(new int[] {st, ed});
return answer.toArray(new int[answer.size()][]);
}
}
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
st, ed := intervals[0][0], intervals[0][1]
var answer [][]int
for _, e := range intervals[1:] {
if ed < e[0] {
answer = append(answer, []int{st, ed})
st, ed = e[0], e[1]
} else if ed < e[1] {
ed = e[1]
}
}
answer = append(answer, []int{st, ed})
return answer
}
复杂度分析
- 时间复杂度：$O(n \log n)$，排序占据主导；之后的扫描每个区间只被访问一次、做常数次比较与赋值，是 $O(n)$。
- 空间复杂度：$O(n)$（不计返回值时为排序所需的 $O(\log n)$ 栈空间）。答案数组最坏情况下要装下全部 $n$ 个互不重叠的区间，这是输出本身的开销。
关键点总结
- 区间类问题的第一反应是排序，因为排序把「任意两个是否重叠」这个全局关系压缩成「相邻两个是否重叠」的局部关系，复杂度立刻从平方级降到线性对数级。
- 按左端点排序之后有一条强结论：一旦当前区间与已合并段分离，后续所有区间也必然分离。这条单调性是只维护一个「当前段」而不必回头的根本依据。
- 右端点扩张必须取
max，因为包含关系会给出一个更小的右端点。任何「用新值直接覆盖累积状态」的写法，都要先确认新值一定不劣。- 闭区间与开区间的语义差别全部体现在判定式的等号上。先问清楚「端点相接算不算重叠」，再决定写
<还是<=。- 「循环内只在遇到分界时结算，循环后必须补最后一段」是所有分段扫描类问题的共同结构，遗漏收尾是这类题最高频的错误。
- 面试视角：主动说明为什么只按左端点排序就够了（右端点的顺序不影响正确性，因为扩张用的是
max），能显示你验证过算法而不是背下来的。- 面试视角：常见追问是 57 题「往已排好的区间集合里插入一个新区间」，答不必重新排序，扫描时分「在新区间左侧、与之重叠、在其右侧」三段处理，$O(n)$ 即可；再进一步的追问是「如何支持动态插入并随时查询」，答用有序集合（TreeMap）按左端点维护，每次插入只需局部合并。
易错点总结
- 错误写法：忘记排序直接扫描。用例
[[2, 6], [1, 3]]→ 第一段为(2, 6)，读到[1, 3]时ed = 6不小于s = 1判定相交，右端点取max(6, 3) = 6，输出[[2, 6]]，正确答案是[[1, 6]]，左端点 1 丢失。- 错误写法：分离判定写成
ed <= s。用例[[1, 4], [4, 5]]→ 两个相接的闭区间被判为分离，输出[[1, 4], [4, 5]]，正确答案是[[1, 5]]。- 错误写法：相交时直接令
ed = e。用例[[1, 10], [3, 5]]→ 右端点被缩回 5，输出[[1, 5]]，正确答案是[[1, 10]]，包含关系被破坏。- 错误写法：循环结束后忘记追加最后一段。用例
[[1, 3], [5, 7]]→ 只有(1, 3)在遇到[5, 7]时被写入，输出[[1, 3]]，正确答案是[[1, 3], [5, 7]]。- 错误写法：分离时先重置
st、ed再追加。用例[[1, 3], [5, 7]]→ 追加进答案的是刚被覆盖的新值(5, 7)，第一段(1, 3)永久丢失。- 错误写法：按右端点排序。用例
[[1, 10], [2, 3], [4, 5]]→ 排序后变成[[2,3],[4,5],[1,10]]，扫描时(2,3)与(4,5)被判为分离而各成一段，输出三段或错误合并，正确答案是[[1, 10]]；左端点序才是保证「分离即永久分离」的那个序。- 错误写法：相交时同时更新左端点为
min(st, s)。用例[[1, 3], [2, 6]]→ 结果虽然正确，但这个min掩盖了「排序已保证st最小」这一事实，一旦排序被误改成右端点序，错误就会被这行代码藏住而难以定位。- 错误写法：用
Arrays.sort(intervals)不给比较器。用例[[1, 3], [2, 6]]→ 二维数组按引用无法自然排序，抛出类型转换异常或得到未定义顺序。- 错误写法：认为需要反复迭代直到不再发生合并。用例
[[1, 4], [2, 5], [3, 6]]→ 排序后一次线性扫描即可得到[[1, 6]]；多轮迭代不但白费 $O(n^2)$ 的代价，还容易在中途修改数组时引入下标错乱。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 56. 合并区间 | 中等 | 与本题同题，是区间排序扫描最基础的样板 |
| 57. 插入区间 | 中等 | 输入已有序，无需排序，改为按左中右三段一次扫描完成插入 |
| 986. 区间列表的交集 | 中等 | 两个有序列表求交而非并，需双指针同步推进并按右端点决定谁前进 |
| 1288. 删除被覆盖区间 | 中等 | 判定的是包含而非相交，排序时右端点需降序作为第二关键字 |
| 253. 会议室 II | 中等 | 求的是最大重叠层数而非合并结果，需要小根堆或差分扫描 |
| 252. 会议室 | 简单 | 只判断是否存在任意重叠，排序后相邻比较一次即可 |
| 759. 员工空闲时间 | 困难 | 先把多人区间合并再取补集，是本题结果之上的一层推导 |
| 763. 划分字母区间 | 中等 | 区间由字符的首末位置隐式给出，需要先构造区间再做同样的扫描 |