扫描线
01 / 一句话本质
把每个区间拆成起点 +1、终点 −1 两个事件, 按位置排序后扫一遍 —— 每碰到一个事件,当前活跃数变一。答案永远是这条阶梯函数的某种性质。
题目同时最多区间数输入[0,30] [5,10] [15,20]
输入有 3 个区间。每个区间在起点贡献一个 +1,在终点贡献一个 −1。
步
0 / 9
活跃
0
峰值
—
0 / 9
02 / 模式骨架
# 区间 → 端点事件events ← []for [s, e] in intervals:events.push((s, +1))events.push((e, −1))events.sort() # 同位置的排序顺序看题目active ← 0; best ← 0for (x, d) in events:active += dbest ← max(best, active)# `best` 就是最大并发数 —— 最经典的答案
03 / 什么时候用这个模式
"同时最多 / 最大并发"
最教科书式的触发词。重叠会议、同时在天上的飞机、高速公路上的车、在班员工 —— 只要你要的是活跃数的峰值。每个区间贡献一对 +1 / −1,剩下的只是清点。
"预订 / 上下车 / 容量"
披着预订列表的容量检查。排序后扫一遍就能看出是否曾经超载, 甚至能在第一次违规处提前返回。
"区间 — 每一点上是什么"
当答案在两个事件之间不变时。阶梯函数只在端点处变化, 所以扫一遍事件就覆盖了时间轴上所有不同的时刻。
"天际线 / 覆盖 / 区间并长度"
扫描线 + 一个辅助数据结构(堆、平衡 BST、multiset)。 每个事件向结构插入或删除一个值;该 x 处的答案就是结构顶端的读数。
04 / 常见坑
i.
同位置事件的排序顺序。
当
+1 和 −1 同 x 时,先处理哪个会改变答案。会议重叠(端点相接算重叠)要先 +1;车上乘客(同站先下后上)要先 −1。骨架一样,平局相反。ii.
跟「区间合并」混淆。
区间合并把重叠区间压成一段、并统计组数;扫描线追踪整条时间轴上的运行深度。 两者都按起点排序,但只有扫描线在意 −1 事件 —— 没有它你看不到深度何时下降。
iii.
忘了事件之间也有运行值。
活跃数在
(prev_x, x] 段内是常数 —— 事件之间什么都没变。 如果题目问「活跃数恰好等于 k 的时长」,要累加 active == k 的区间长度, 而不是事件个数。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。