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

将区间转成排序事件,并用端点处理次序表达重叠规则。

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

扫描线Sweep Line

按坐标排序事件,维护活跃区间;同坐标事件的处理顺序决定边界语义。

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

本课要建立的能力

将区间转成排序事件,并用端点处理次序表达重叠规则。

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

01先把问题说具体

会议时段为 [1,4)、[2,5)、[4,6),同时最多需要几间会议室?

02一步步得到方法

把区间内部的连续变化压缩到事件

没有会议开始或结束时,占用数量不变,因此只需关注端点。开始事件 +1,结束事件 −1,按时间排序后扫描,active 表示当前占用,最大 active 就是峰值。

这与差分思想相同,但时间坐标可能巨大而稀疏,不能按每个时间单位开数组。扫描线只排序实际发生变化的坐标,成本取决于事件数而非坐标范围。

同一时刻谁先处理决定语义

半开区间在结束时刻已释放资源;时间 4 时,第一场结束后第三场可以使用同一间房。因此同坐标先处理结束 −1,再处理开始 +1。

若统计闭区间端点上的重叠,顺序应相反。或者按坐标汇总开始与结束数,明确在何时采样峰值;不能让语言排序的偶然行为替代定义。

同一坐标事件要作为一组思考

把连续空间的问题转成有序事件后,两个相邻事件之间活跃集合不变;最大重叠数等量只需在状态变化时检查。坐标跨度很大并不妨碍事件只有 O(n) 个。

相同坐标的开始和结束次序与区间语义绑定。半开区间一般先处理结束,再处理开始;闭区间若端点接触也算覆盖,需要另一约定。不要只依赖排序的默认平局顺序。

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

会议 [1,4)、[2,5)、[4,6)。

步骤计算与状态为什么这样做
t=1、2active=1、2两场重叠
t=4,先结束active 从 2 降至 1[1,4) 已不占用
t=4,再开始active 回到 2新会议复用资源
t=5、6active=1、0峰值 2

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

答案是 2,不是 3;端点语义会直接改变结果。

04为什么这个方法成立

  1. 每次事件后 active 等于已经开始且尚未结束的会议数。
  2. 半开语义下先结束再开始,不会计算不存在的瞬时重叠。
  3. 占用只在事件时变化,扫描所有事件就不会漏掉最大值。

05把推导翻译成代码

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

def rooms(intervals):
    events = []
    for start, end in intervals:
        if start > end:
            raise ValueError("invalid interval")
        if start == end:
            continue
        events.extend([(start, 1), (end, -1)])
    active = answer = 0
    for time, delta in sorted(events):
        active += delta
        answer = max(answer, active)
    return answer

逐个理解关键决定

(end, -1)
元组排序在同时间把 −1 放到 +1 前,显式实现半开语义。
start == end
空时段不占资源,应忽略,避免先结束出现负计数。

06时间、空间与实现范围

2n 个事件排序 O(n log n),扫描 O(n),事件空间 O(n)。

更复杂的扫描线如矩形并面积还需维护覆盖长度结构,不能仅用 active 个数替代。

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

只求总开始数减总结束数

这只得到最终占用 0,丢失峰值随时间变化的信息。

把坐标值当作事件数量

扫描事件的复杂度取决于端点数和维护结构,不一定需要遍历最小到最大坐标间所有整数。

08从手算到独立迁移

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

练习 1 · 复现与理解

[1,2)、[2,3) 需要几间?

需要一点提示

先释放再申请。

查看解析与答案

1 间。

练习 2 · 边界与辨析

相同两场 [1,3) 需要几间?

需要一点提示

同时开始且持续。

查看解析与答案

2 间,事件不能去重。

练习 3 · 变式与迁移

要输出达到峰值的时间段,需加什么?

需要一点提示

相邻事件坐标间计数不变。

查看解析与答案

按坐标处理后记录到下一个不同坐标的区间及 active,再筛选最大占用区间。

继续深入这个专题

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

MIT 6.006 · 算法讲义

理解之后,继续递进

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