系列导航：LeetCode Hot100 刷题导航（系列导航） · 上一篇：Hot100 53 | 最大子数组和：暴力到动态规划入门 · 下一篇：Hot100 189 | 轮转数组：额外数组到三次反转

这题表面上看只是一个“把区间整理一下”的数组题，但它真正训练你的其实是两件事：

  • 什么时候应该先排序
  • 排序之后，怎么把原本看起来很乱的关系变成线性处理

专栏导读

这题很适合作为“排序后处理结构关系”的入门题。

因为很多新手第一次看到区间题时，脑子里会同时装着很多问题：

  • 这个区间和那个区间会不会重叠
  • 我是不是要回头反复比较前面的所有区间
  • 一旦重叠了，到底是新增，还是修改旧结果

这篇会重点讲清楚下面几件事：

  1. 什么叫区间重叠
  2. 为什么必须先排序
  3. 为什么只需要看“结果数组最后一个区间”
  4. merged[-1] 到底代表什么
  5. 为什么这题不是“到处两两比较”，而是“一路吞并”

1. 题目到底在说什么

题目给你若干个区间，例如：

1
[[1,3],[2,6],[8,10],[15,18]]

每个区间都表示：

  • 从起点到终点的一段范围

如果两个区间有重叠，就要把它们合并成一个更大的区间。

上面这个例子里：

  • [1,3] 和 [2,6] 有重叠

所以它们应该合并成：

1
[1,6]

于是最终结果是：

1
[[1,6],[8,10],[15,18]]

2. 什么叫“重叠”

这题第一眼最容易糊涂的，其实不是代码，而是“什么时候算重叠”。

假设有两个区间：

  • [a, b]
  • [c, d]

如果第二个区间的起点 c 小于等于第一个区间的终点 b，那它们就有重叠。

例如：

  • [1,3] 和 [2,6]

因为：

1
2 <= 3

所以它们重叠。

但如果是：

  • [1,3] 和 [4,6]

因为：

1
4 > 3

那它们就是分开的，不能合并。

3. 这题最容易误解的点

很多人第一次做这题，会下意识去想：

  • 我是不是得把当前区间和前面所有区间都比较一遍？

如果你这样想，题目会显得很乱。

其实这题真正的关键是：

  • 先排序

只要先按区间起点排序，后面的处理就会一下子变得很简单。

4. 为什么必须先排序

如果区间顺序是乱的，你根本不知道：

  • 后面的新区间到底会和谁发生关系

但一旦按起点排序，就会有一个非常重要的性质：

  • 后面出现的区间，起点一定不会比前面的更小

这意味着什么？

意味着你从左到右处理时，当前区间只可能和“当前正在维护的最后一个合并区间”发生关系，不需要回头反复看很久以前的区间。

这就是这题真正变简单的原因。

5. 先把题目翻译成人话

如果把这题翻译成最直白的话，其实就是：

  1. 先按区间起点排序
  2. 从左到右一个一个读区间
  3. 看它能不能接到当前结果的最后一段后面
  4. 如果能接，就把最后一段延长
  5. 如果不能接，就新开一段

你可以把它想成：

  • 不是在“比较所有区间”
  • 而是在“维护一段当前可吞并的区间”

6. 最直观的想法：排序后逐段合并

6.1 为什么这个思路天然成立

排序以后，我们维护一个结果数组 merged。

每当读到一个新区间 interval 时，只会有两种情况：

  1. 它和 merged 里最后一个区间不重叠
  2. 它和 merged 里最后一个区间重叠

如果不重叠：

  • 说明它必须独立开一段

如果重叠：

  • 说明它应该把最后一段往右扩展

这就是整题最核心的二分逻辑。

7. Python Tutor 版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []

    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

print(merge([[1,3],[2,6],[8,10],[15,18]]))

8. LeetCode 可提交版代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        merged = []

        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

9. 每一行代码在做什么

先看排序：

1
intervals.sort(key=lambda x: x[0])

这里的 x[0] 表示每个区间的起点。

所以这一句的含义是：

  • 按区间起点从小到大排序

为什么一定是按起点排？

因为后面我们从左到右合并时，最需要保证的是：

  • 新区间出现顺序是按开始位置递增的

这样才方便判断它和当前最后区间的关系。

再看：

1
merged = []

这里的 merged 表示：

  • 已经合并好的结果数组

你可以把它理解成：

  • 目前已经整理好的区间列表

接下来遍历排序后的所有区间：

1
for interval in intervals:

这里的 interval 就是当前读到的新区间。

最关键的是这个判断：

1
if not merged or merged[-1][1] < interval[0]:

这句话有两层含义。

9.1 第一层：not merged

表示：

  • 如果结果数组还是空的
  • 那当前区间一定直接放进去

因为你还没有任何已合并区间可以和它比较。

9.2 第二层：merged[-1][1] < interval[0]

这里：

  • merged[-1] 表示结果数组最后一个区间
  • merged[-1][1] 表示最后一个区间的终点
  • interval[0] 表示当前新区间的起点

如果：

1
最后一个区间的终点 < 当前区间的起点

那就说明：

  • 当前区间和最后一个区间完全分开
  • 它们之间没有重叠

于是直接：

1
merged.append(interval)

表示新开一段。

再看重叠时的处理：

1
merged[-1][1] = max(merged[-1][1], interval[1])

这句的意思是：

  • 当前新区间和最后一段有重叠
  • 所以不需要新增区间
  • 只需要把最后一段的终点尽量往右延长

为什么只改终点，不改起点？

因为：

  • 排序后，最后一段的起点一定不大于当前新区间的起点
  • 所以合并后的起点仍然是旧的起点

真正需要更新的是谁更靠右的终点。

10. 用示例手动走一遍

示例：

1
[[1,3],[2,6],[8,10],[15,18]]

先按起点排序后，顺序刚好不变：

1
[[1,3],[2,6],[8,10],[15,18]]

第一步：处理 [1,3]

这时 merged 还是空的，所以直接加入：

1
merged = [[1,3]]

第二步：处理 [2,6]

看最后一个区间：

  • 最后一个是 [1,3]
  • 当前是 [2,6]

判断是否重叠：

1
3 < 2 ?

答案是否定的。

因为 3 并没有小于 2，说明它们有重叠。

于是更新最后一个区间终点：

1
merged = [[1,6]]

第三步：处理 [8,10]

现在最后一个区间是 [1,6]。

判断：

1
6 < 8

成立，说明没有重叠。

于是新开一段：

1
merged = [[1,6],[8,10]]

第四步：处理 [15,18]

看最后一个区间 [8,10]：

1
10 < 15

成立，还是不重叠。

所以再新开一段：

1
merged = [[1,6],[8,10],[15,18]]

这就是最终答案。

11. 为什么只需要看最后一个区间

这是这题第一次学时最值得想清楚的地方。

很多人会问：

  • 为什么当前区间不用和 merged 里更早的区间再比较？

答案是：

  • 因为我们已经按起点排序了

所以如果当前区间连最后一个区间都接不上，那它更不可能回头去和更早的区间接上。

因为更早的区间终点只会更靠左，关系只会更远。

所以：

  • 排序 + 只看最后一个结果区间

这两个动作是一整套逻辑，不是两个独立技巧。

12. 这题顺手学到的 Python 语法

12.1 sort(key=...)

1
intervals.sort(key=lambda x: x[0])

表示按每个区间的起点排序。

12.2 merged[-1]

表示列表最后一个元素。

在这题里，它表示：

  • 当前已经合并好的最后一段区间

12.3 max(a, b)

用来决定合并后终点应该延长到哪里。

13. 这题最容易犯的错

13.1 忘了先排序

如果不排序，后面“只看最后一个区间”这个逻辑就不成立了。

13.2 重叠时错误地 append

如果本来应该合并，你却又 append 一个新区间，就会把本该合并的区间分裂开，答案自然错误。

13.3 不理解 merged[-1] 的角色

它不是随便取最后一个元素，而是“当前正在维护、可能继续被延长的那一段”。

13.4 合并时错误改了起点

排序后通常不需要改起点，真正要更新的是终点。

14. 一句话复盘

这题的本质不是把区间两两乱比，而是先按起点排序，再从左到右维护“当前最后一段”，能吞并就吞并，不能吞并就新开一段。

15. 下一步怎么学

下一题 189. 轮转数组 会继续留在数组专题，但重点会从“排序后看关系”切到“原地修改数组结构”。