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、2 | active=1、2 | 两场重叠 |
| t=4,先结束 | active 从 2 降至 1 | [1,4) 已不占用 |
| t=4,再开始 | active 回到 2 | 新会议复用资源 |
| t=5、6 | active=1、0 | 峰值 2 |
窄屏可左右滑动表格,阅读完整计算与理由。
答案是 2,不是 3;端点语义会直接改变结果。
04为什么这个方法成立
- 每次事件后 active 等于已经开始且尚未结束的会议数。
- 半开语义下先结束再开始,不会计算不存在的瞬时重叠。
- 占用只在事件时变化,扫描所有事件就不会漏掉最大值。
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,2)、[2,3) 需要几间?
需要一点提示
先释放再申请。
查看解析与答案
1 间。
相同两场 [1,3) 需要几间?
需要一点提示
同时开始且持续。
查看解析与答案
2 间,事件不能去重。
要输出达到峰值的时间段,需加什么?
需要一点提示
相邻事件坐标间计数不变。
查看解析与答案
按坐标处理后记录到下一个不同坐标的区间及 active,再筛选最大占用区间。