专题进阶 · 数组技巧推荐总顺序 · 第 40 / 148 课

排序后维护当前最右端点,严格区分闭区间与半开区间相接的语义。

先学会这些,再进入本课 插入排序
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数组技巧

区间合并Merge Intervals

按左端点排序后扫描,用当前右边界合并重叠区间。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

排序后维护当前最右端点,严格区分闭区间与半开区间相接的语义。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

合并闭区间 [1,3]、[2,6]、[8,10]、[10,12],得到覆盖相同点集合的最少连续区间。

02一步步得到方法

排序消除回头检查

先按左端点升序排序。扫描到新区间 [l,r] 时,如果 l≤当前区间右端点,就存在重叠或共享端点,将右端点更新为 max(old,r)。否则两者之间有空隙,当前区间可以安全输出。

max 不能省略:新区间可能完全包含在当前区间内部,比如 [1,10] 后接 [2,3],若直接把右端改成 3,会丢掉 3 到 10 的覆盖。

先声明端点规则

本课使用闭区间,所以 [1,2] 与 [2,3] 共享点 2,可合并。若题目是占用时段 [start,end),相接不等于同时占用;是否为了表示并集而仍合并相接区间,要由输出需求决定。

为什么只需记住最后一段

按左端点排序后,未来区间的起点不会更早。若当前区间与输出最后一段不相交,就更不可能跨过它去与更早的已结束区间相交,所以只比较最后一段即可。

是否把端点相等视为重叠取决于语义。闭区间 [1,2] 与 [2,3] 共享点;预约采用半开区间时,前一场在2结束、后一场在2开始可以不冲突。代码条件必须对应题意。

03把一个小例子完全算清楚

闭区间 [[1,3],[2,6],[8,10],[10,12]]。

步骤计算与状态为什么这样做
读 [1,3]当前 [1,3]初始化
读 [2,6]当前 [1,6]2≤3,扩大右端
读 [8,10]输出 [1,6],当前 [8,10]8>6,中间有空隙
读 [10,12]当前 [8,12]共享端点 10

窄屏可左右滑动表格,阅读完整计算与理由。

结果 [[1,6],[8,12]];合并改变表示方式,不改变覆盖集合。

04为什么这个方法成立

  1. 当前区间始终是尚未输出的重叠链的完整并集。
  2. 新区间起点在右端之外时,后续起点只会更大,不可能再与当前区间连接。
  3. 因此输出后无需回头,最终每个区间被完整覆盖且结果互不重叠。

05把推导翻译成代码

Python · 可独立运行的教学实现

def merge_intervals(intervals):
    result = []
    for left, right in sorted(intervals):
        assert left <= right
        if not result or left > result[-1][1]:
            result.append([left, right])
        else:
            result[-1][1] = max(result[-1][1], right)
    return result

逐个理解关键决定

sorted(intervals)
扫描安全性来自左端点有序,不能直接套用原始顺序。
max(result[-1][1], right)
同时处理延伸和包含两种关系。

06时间、空间与实现范围

排序 O(n log n),扫描 O(n),输出与排序副本最多 O(n) 空间。

如果输入已按左端点排序且可流式读取,合并本身只需一次线性扫描。

07改变条件,检查哪里会出错

把区间合并当作最大不重叠区间选择

前者保留全部覆盖,后者丢弃部分区间以最大化数量,目标不同。

直接修改调用者的区间列表

原地排序或复用内层列表会改变输入;若接口承诺保留输入,应复制需要修改的结构。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[[1,10],[2,3]] 输出什么?

需要一点提示

第二个被包含。

查看解析与答案

[[1,10]]。

练习 2 · 边界与辨析

闭区间 [2,2] 是否为空?

需要一点提示

左右端点都包含。

查看解析与答案

不是,包含点 2;与半开 [2,2) 不同。

练习 3 · 变式与迁移

如何计算合并后的总连续长度?

需要一点提示

对不重叠结果求差。

查看解析与答案

连续长度求 Σ(r−l);若统计整数点且闭区间不重叠,则求 Σ(r−l+1),先明确度量。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。