输入#

二维整数数组 intervals，每个元素是 [start_i, end_i] 表示一个区间

输出#

合并重叠后的区间数组

约束条件#

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

示例1#

1
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
2
输出：[[1,6],[8,10],[15,18]]

解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

示例2#

1
输入：intervals = [[1,4],[4,5]]
2
输出：[[1,5]]

解释：区间 [1,4] 和 [4,5] 在端点 4 处相接，视为重叠区间，合并为 [1,5]。

从暴力枚举出发#

最朴素的想法是：反复扫描所有区间对，发现重叠就合并，合并后重新扫描，直到没有任何区间可以合并为止：

1
class Solution:
2
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3
        if not intervals:
4
            return []
5

6
        res = []
7
        used = [False] * len(intervals)
8

9
        for i in range(len(intervals)):
10
            if used[i]:
11
                continue
12
            l, r = intervals[i]
13
            # 反复扫描，不断扩展当前区间，直到无法再扩展
14
            changed = True
15
            while changed:
16
                changed = False
17
                for j in range(len(intervals)):
18
                    if used[j]:
19
                        continue
20
                    a, b = intervals[j]
21
                    if a <= r and l <= b:      # 发现重叠
22
                        l = min(l, a)
23
                        r = max(r, b)
24
                        used[j] = True
25
                        changed = True
26
            res.append([l, r])
27

28
        return res

以每个未合并区间为起点，反复扫描剩余区间并不断吞并重叠者。最坏情况下（区间呈”链式重叠”，每次只合并一个），复杂度达到 $O(n^2)$。

瓶颈分析：暴力法花了大量时间在”寻找与当前区间重叠的下一个区间”上——区间是无序的，每次都要全量扫描。如果能让区间按某种顺序排列，使得可能重叠的区间彼此相邻，一次从左到右的扫描就能完成所有合并。

🧠 直觉理解：想象你面前有一堆纸条，每张纸条写着起止时间，散乱地摊在桌上。暴力法是你随手拿起一张，然后翻遍全桌找能和它接上的——找到一张接一张，接不上了再换下一张。如果先把纸条按起始时间从左到右排好，你会发现——能合并的纸条一定彼此相邻，从左到右一趟就能全部处理完。

排序 + 贪心扫描#

将所有区间按起点升序排序后，一个关键性质浮出水面：

性质：排序后，如果当前区间 $[x, y]$ 不能与前面正在合并的区间 $[l, r]$ 合并（即 $x > r$），那么后面所有的区间也不可能与 $[l, r]$ 合并——因为后面的起点只会更大。

这意味着我们可以用”甩手掌柜”的方式处理：维护一个”当前正在合并”的区间 $[l, r]$，从左到右扫描每个区间——

• 如果 $x \le r$（重叠），就扩展右边界：$r = \max(r, y)$
• 如果 $x > r$（不重叠），就把 $[l, r]$ 存入结果，然后开启一个新的合并区间 $[l, r] = [x, y]$

扫描结束后，别忘了把最后一个 $[l, r]$ 也存进去。

1
class Solution:
2
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3
        intervals.sort()           # 按起点排序
4
        res = []
5
        l, r = intervals[0]        # 当前正在合并的区间
6

7
        for x, y in intervals:
8
            if x <= r:              # 重叠：扩展右边界
9
                r = max(r, y)
10
            else:                   # 不重叠：封存当前区间，开启新区间
11
                res.append([l, r])
12
                l, r = x, y
13

14
        res.append([l, r])          # 封存最后一个区间
15
        return res

⚠️ 注意：intervals.sort() 对二元列表默认按第一个元素排序，第一个相同时按第二个元素排序。这里我们只需要按起点排序，intervals.sort() 刚好满足。如果面试官要求显式表达，可以写成 intervals.sort(key=lambda x: x[0])。

复杂度#

• 时间复杂度：$O(n \log n)$，其中 $n$ 是区间个数。排序占 $O(n \log n)$，扫描占 $O(n)$。
• 空间复杂度：$O(1)$（不计输出数组 res），或 $O(n)$（计入输出）。仅使用了 l、r 两个额外变量。

$O(n \log n)$ 已是理论最优——因为区间合并问题至少需要排序，而比较排序的下界就是 $O(n \log n)$。如果输入本身已按起点有序（如某些变体题目的设定），则可做到 $O(n)$。

⚠️ 注意：Python 的 list.sort() 是原地排序，空间复杂度为 $O(1)$（TimSort 的临时空间为 $O(n)$ 但通常不计入）。如果你不希望修改输入数组，可以 sorted(intervals) 代替，但空间变为 $O(n)$。

写法对比：l, r vs res[-1]#

上面使用了 l, r 两个变量追踪正在合并的区间。另一种常见写法是直接在结果数组的最后一个区间上操作：

1
class Solution:
2
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3
        intervals.sort()
4
        res = [intervals[0]]
5

6
        for x, y in intervals[1:]:
7
            if x <= res[-1][1]:
8
                res[-1][1] = max(res[-1][1], y)
9
            else:
10
                res.append([x, y])
11

12
        return res

两种写法的对比：

l, r 版本的好处是思路更清晰——“我正在合并一个区间，还没想好要不要放进结果”。res[-1] 版本的好处是代码更紧凑——边界处理被 res 初始化吃掉，循环从 intervals[1:] 开始，省去了尾部的那句 res.append([l, r])。

💡 小贴士：在面试中建议先写出 l, r 版本，把思路讲清楚；如果面试官要求更简洁，再优化到 res[-1] 版本。一上来就甩出 res[-1] 可能会让面试官觉得你在背模板。

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

两种写法在本题中完全等价——因为 Python 的列表比较是按元素顺序逐个比较的：

• [1, 3] < [2, 6] 先比第一个元素 1 < 2，结果为 True，不再比第二个
• [1, 3] < [1, 4] 第一个相等 1 == 1，比第二个 3 < 4

这意味着 intervals.sort() 等价于 “按起点排序，起点相同时按终点排序”。而题目只需要按起点排序——起点相同时按终点排不排都不影响正确性，但恰好也能正常工作。

显式写成 key=lambda x: x[0] 的好处是意图表达更明确，但性能上反而略慢（多了 lambda 调用开销）。两种写法都可以，看个人偏好。

处理空输入#

虽然约束条件保证 n >= 1，但在工程实践中防御式编程不会错：

1
class Solution:
2
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3
        if not intervals:
4
            return []
5
        # ...

如果约束真的可能为 0，intervals[0] 会在初始化 l, r 时抛出 IndexError。