LC56　合并区间¶

中等通过率 54%python3核心代码模式普通数组样例通过牛客 AC数组排序快速排序

牛客原题　源码

讲解章节：排序

一句话

按左端点排序后一趟扫描，能接上就把当前区间的右端点往外撑。

解题思路¶

这题考什么¶

两个区间 [a1, b1] 与 [a2, b2] 有交叠的条件是 a1 <= b2 且 a2 <= b1，在乱序的输入上判断任意两个是否重叠要 O(n^2) 对，而且合并出的新区间还可能与之前已经排除过的区间重新产生交叠，得反复扫。

先按左端点升序排序，这个麻烦就消失了。排序之后有一条关键性质：

扫到第 i 个区间时，它的左端点不小于前面所有区间的左端点。
于是它要么与「当前正在攒的那个合并区间」相交（左端点落在其内部或右端点上），
要么整个落在它右边——**不可能与更早的、已经封存的区间再产生交叠**，
因为那些区间的右端点只会更靠左。

所以只需要维护「最后一个已输出的区间」，每来一个新区间做二选一：

新区间左端点 <= 最后一个区间的右端点   -> 相交，把右端点扩成两者的较大值
否则                                   -> 断开了，把新区间原样追加

这是典型的排序 + 贪心一趟扫（见排序与贪心），与区间调度、活动选择是同一族问题。注意那一族常按右端点排序（要选最多的不相交区间），本题按左端点排序，因为要的是把相邻的连成一片，得让扫描顺序与区间在数轴上的先后一致。

另一条路是差分/扫描线（见前缀和与差分）：把左端点记 +1、右端点记 -1，排序后累加，计数从 0 变正的位置是一段的开头、回到 0 的位置是结尾。它能处理更一般的「覆盖次数」问题，但本题只要合并，上面的一趟扫更短也更直观；而且端点闭合语义（[1,4] 与 [4,5] 算相接）在差分写法里需要额外约定同一坐标上 +1 先于 -1，反而容易出错。

数据规模与复杂度¶

1 <= n <= 1e4，区间端点满足 0 <= start_i <= end_i <= 1e4。时间 O(n log n)，瓶颈在排序；扫描本身是 O(n)。空间 O(n) 存答案（Python 的 list.sort 是原地的 Timsort，排序本身不额外占 O(n)）。两两比较合并的朴素做法是 O(n^2) = 1e8 对，还要反复迭代到不动点，Python 下太慢。

坑在哪¶

参数是二维数组，不是区间对象。每个区间就是长度 2 的 list，用 intervals[i][0] / intervals[i][1] 取端点。牛客 BM89 的同名题给的是 Interval 类、要写 .start / .end，两边的代码不能直接搬。
相接算重叠，判据必须带等号：start <= ans[-1][1]。用严格小于的话，样例 2 的 [1,4] 与 [4,5] 会被当成两段输出 [[1,4],[4,5]]，而期望是 [[1,5]]。
扩右端点要取 max，不能无脑赋值。[[1,10],[2,3]] 排序后仍是这个顺序，若直接把右端点写成 3，就会把 [1,10] 缩成 [1,3]——包含关系的区间必须留住外层的。
追加时要 ans.append([start, end]) 新建一个 list，不要把输入的那一行直接挂进答案。挂进去之后第 3 步的扩端点会顺手改写入参，若调用方之后还要用原数组就会读到被污染的数据。
排序键只取左端点即可。左端点相同时右端点的先后不影响结果—— 反正下一步就会被 max 撑到两者的较大值。
输入不保证有序，样例 3 的 [[4,7],[1,4]] 就是乱的。省掉排序直接扫，它会被当成两段互不相交的区间输出，而期望是 [[1,7]]。
严格比对：排序后一趟扫产生的结果天然按左端点升序，与力扣的期望输出顺序一致，不需要特判顺序（本题在 meta.json 的 judge 里没有配 unordered）。

样例复核¶

intervals = [[1,3],[2,6],[8,10],[15,18]]，期望 [[1,6],[8,10],[15,18]]。排序后不变。逐个扫：

[1,3]   答案为空，直接追加                   ans = [[1,3]]
[2,6]   2 <= 3，相交，右端点 max(3, 6) = 6   ans = [[1,6]]
[8,10]  8 > 6，断开，追加             ans = [[1,6], [8,10]]
[15,18] 15 > 10，断开，追加           ans = [[1,6], [8,10], [15,18]]

与样例一致。样例 3 的 [[4,7],[1,4]] 排序后变成 [[1,4],[4,7]]，第二步 4 <= 4 成立（等号在这里救了场），合并成 [1,7]，同样一致。

参考实现¶

solutions/leetcode/LC56/sol.py
from typing import List, Optional


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 按左端点升序。排序之后才有那条关键性质：新区间只可能与
        # 「最后一个已输出的区间」相交，不会回头与更早的区间重新交叠。
        # 输入本身不保证有序（样例 3 就是 [[4,7],[1,4]]），这一步不能省
        intervals.sort(key=lambda seg: seg[0])
        ans = []
        for seg in intervals:
            start = seg[0]
            end = seg[1]
            # 相接也算重叠，等号必须带：没有等号时 [1,4] 与 [4,5] 会被拆成两段
            if ans and start <= ans[-1][1]:
                # 取较大者，不能直接赋值：[[1,10],[2,3]] 里若把右端点写成 3，
                # 就把外层的 [1,10] 缩掉了
                if end > ans[-1][1]:
                    ans[-1][1] = end
            else:
                # 与前一段完全断开，另起一段。
                # 新建 list 而不是把输入那一行挂进来，避免上面扩端点时改写入参
                ans.append([start, end])
        return ans

LC56 合并区间¶