BM89　合并区间¶

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

讲解章节：排序

一句话

按起点排序后一遍扫描，接得上就撑大右端点，接不上就另起一段。

解题思路¶

这题考什么¶

排序把「与谁可能重叠」从全局问题变成局部问题。乱序时任意两个区间都要判交，是 O(n^2)；按起点升序排完之后有一条关键性质：一旦某个区间的起点越过了当前正在生长的那一段的右端点，它之后的所有区间起点只会更大，必然也接不上。于是「当前段还能不能继续长」只取决于紧邻的下一个区间，一次线性扫描就够。

维护一个「当前正在生长的区间」cur：

it.start <= cur.end  ->  有重叠（含端点相接），cur.end = max(cur.end, it.end)
it.start >  cur.end  ->  断开了，把 cur 收进答案，cur 换成 it

走一遍 [[10,30],[20,60],[80,100],[150,180]]（已按起点有序）：

cur=[10,30]
[20,60]    20 <= 30  重叠 -> cur=[10,60]
[80,100]   80 >  60  断开 -> 收 [10,60]，cur=[80,100]
[150,180] 150 > 100  断开 -> 收 [80,100]，cur=[150,180]
扫完 cur 仍在手上          -> [[10,60],[80,100],[150,180]]

本实现把结果列表的末尾元素直接当作 cur（out[-1] 就是「正在生长的那一段」），于是「收进答案」这一步天然完成，也就不存在「循环结束后忘了补收最后一段」这个最常见的漏项。

数据规模与复杂度¶

区间组数 n <= 2e5，端点值 0 <= val <= 2e5，时限「其他语言 4 秒」。时间 O(n log n)，瓶颈在排序，扫描只有 O(n)；空间 O(n)（结果列表）加上排序自身的 O(log n) 栈开销。题面的进阶要求是 O(val) 时间与空间，指的是端点值域只有 2e5，可以在值域上开差分数组扫一遍绕开排序；n 与 val 同量级时收益有限， 4 秒时限下排序法足够宽裕。相关章节见排序。

坑在哪¶

参数与返回都是 Interval 对象（带 .start 与 .end 两个属性），不是二元组。按 it[0] / it[1] 取值会直接 TypeError。本实现复用输入对象、只改它的 .end，既省掉构造，也不必依赖判题环境有没有把 Interval 这个名字暴露给题解模块。
重叠时右端点必须取两者较大者，不能直接赋成新区间的 end。存在被完全包含的区间：[10,60] 之后来了 [20,30]，直接赋值会把右端点缩回 30，接下来的 [40,50] 就会被误判成断开，多输出一段。
端点相接算重叠，判断用 <= 而不是 <。样例里 [[0,10],[10,20]] 的答案是 [[0,20]]。
题面要求合并后按区间起点升序输出。排序已经保证了这一点，扫描过程只会往结果尾部追加起点更大的段，顺序天然正确，末尾不必再排一次。
空输入要先挡住：题面允许 n = 0，而 intervals[0] 会在空列表上越界。
排序是原地的，会改动调用方传进来的那个列表。本题判题只看返回值，没有影响，但把「输入不可变」当默认假设的写法在别处会踩雷。

参考实现¶

solutions/nowcoder/BM89/sol.py
from typing import List, Optional


class Solution:
    def merge(self, intervals: "List[Interval]") -> "List[Interval]":
        # 题面允许 n = 0，先挡住空输入，否则下面取 intervals[0] 越界
        if not intervals:
            return []

        # 按起点升序排序：重叠关系随之变成只与相邻元素有关的局部性质，
        # 同时顺带满足题面「合并后按区间起点升序」的输出要求
        intervals.sort(key=lambda it: it.start)
        out = [intervals[0]]                 # 末尾元素就是「当前正在生长的区间」
        # 从第 2 个区间起逐个尝试并入，切片起点 1 是因为首个已经在 out 里
        for it in intervals[1:]:
            cur = out[-1]
            if it.start <= cur.end:          # 端点相接也算重叠，所以是 <= 而非 <
                # 右端点取较大者：存在被完全包含的区间，直接赋值会把它缩回去
                if it.end > cur.end:
                    cur.end = it.end
            else:                            # 起点越过右端点，后面的只会更远，另起一段
                out.append(it)
        return out

BM89 合并区间¶