几何、扫描线、模拟与解析 · HTML
数学 / 逻辑形态
每个对象产生 start/end 事件；按 coordinate 与 tie rule 排序，应用 delta 后在下一坐标前状态恒定。
识别信号
- 区间重叠或并发峰值
- 开始结束事件天然存在
- 相邻坐标间状态不变
- 需要并集长度或覆盖次数
- 几何对象可沿一轴扫描
容易误判的相似信号
| Signal | Why it is different |
|---|
| 事件顺序依赖原输入 | 若过程不是按坐标可交换，排序会改变语义，应做显式模拟。 |
| 动态二维活动结构很复杂 | 扫描线只降一维，另一维仍可能需要 segment tree 等结构。 |
核心不变量
处理坐标 x 的全部事件后，active 精确表示开区间 (x,next_x) 上的活动对象。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 排序事件 (x,delta)、当前 active、最佳值或累计 measure、前一坐标 prev。 |
| Transition | 先用旧 active 结算 prev 到 x 的区间，再按统一 tie rule 合并 x 上所有 delta。 |
| Frontier / order | 扫描坐标将已结算左侧与未处理右侧分开；状态只在事件点改变。 |
Python 骨架
def max_overlap(half_open_intervals):
events = []
for left, right in half_open_intervals:
if left < right:
events.append((left, 1))
events.append((right, -1))
active = best = 0
# For [left,right), endings at x happen before starts at x.
for _, delta in sorted(events, key=lambda e: (e[0], e[1])):
active += delta
best = max(best, active)
return best
def covered_length(intervals):
events = sorted((x,d) for l,r in intervals for x,d in ((l,1),(r,-1)) if l < r)
active = total = 0; prev = None
for x, delta in events:
if prev is not None and active: total += x-prev
active += delta; prev = x
return total
正确性思路
- 活动状态只可能在端点改变。
- 相邻事件坐标间没有变化，旧 active 对整段有效。
- 端点 delta 加总后得到下一开放段的精确活动数。
- 遍历全部事件段，因此峰值或长度不重不漏。
复杂度
| Time | Space | Parameters |
|---|
| O(E log E) | O(E) | E 为事件数，通常是对象数的常数倍 |
边界条件
- 半开与闭区间 tie rule 不同
- 同坐标多个事件应批量理解
- 零长度区间
- 负坐标
- 长度结算必须在更新 active 前
错误模式
| Pattern | Why it fails / fix |
|---|
| 同点先后顺序错误 | 半开区间应让结束先于开始。 |
| 先更新再结算长度 | 会把新状态错误应用到左侧区间。 |
| 只按坐标不定 tie | 并发峰值会随排序稳定性偶然变化。 |
选择与排除规则
- 状态只在端点变：扫描线。
- 只需最大重叠：delta 计数即可。
- 需动态维护另一维：组合 segment tree。
- 先写清区间闭开语义，再设计 tie rule。
相关模板
| Relation | Template | Boundary |
|---|
| analogy | 归并排序跨区间计数 | 排序一个维度，维护另一个维度的活动关系。 |
| 活动结构 | 线段树区间聚合 | 扫描中需维护动态区间摘要 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最大重叠为 2。 |
| Scenario | 半开区间 [1,4)、[2,5)、[4,6)。 |
| Walkthrough | 坐标 4 先结束第一段再开始第三段，因此不会错误得到 3。 |
Recall prompts
我的补充