贪心与调度 · HTML
数学 / 逻辑形态
对半开区间 I=[s,e)。选择型常按 e 递增，若 s>=last_end 就接受；合并/覆盖型常按 s 递增并维护最远终点。排序键和端点语义必须来自目标。
识别信号
- 对象可表示为一维开始/结束区间。
- 目标涉及不重叠、删除冲突、合并覆盖或最少资源。
- 排序后少量边界即可描述已处理前缀。
- 更早结束为后续留下不少于其他选择的空间。
- 可用 exchange argument 证明局部选择。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 带权区间选择 | 价值不同后，最早结束不保证最大总价值；通常需 DP 加二分前驱。 |
| 任意冲突图 | 冲突若不是一维相交，单个端点无法概括未来。 |
| 动态插入删除 | 一次排序扫描不支持在线变化，需要平衡树或区间数据结构。 |
核心不变量
处理完排序前缀后，已选方案在相同选择数下具有不晚于任何替代方案的结束边界，因此为未处理区间保留最大可用空间。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 已排序区间、边界 last_end 与答案；覆盖变体还可维护 current_end/farthest。 |
| Transition | 新区间兼容则接受并更新边界；冲突时保留对未来约束更小的区间，选择型通常保留结束更早者。 |
| Frontier / order | 由证明决定的端点排序顺序；选择常按结束，合并与覆盖常按开始。 |
Python 骨架
def max_compatible(intervals):
# Half-open intervals [start, end).
ordered = sorted(intervals, key=lambda p: (p[1], p[0]))
chosen = []
last_end = float('-inf')
for start, end in ordered:
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
正确性思路
- 令 g 为结束最早的可行区间，任一最优解首项为 o，则 end(g)<=end(o)。
- 用 g 替换 o 不会使原来位于 o 之后的区间失效，且选择数不变。
- 删除 g 覆盖的前缀后得到同型子问题；反复交换即可得到完整贪心最优解。
复杂度
| Time | Space | Parameters |
|---|
| O(n log n)，扫描 O(n) | O(n) 保存排序/答案；原地排序可更低 | n 为区间数；闭合语义决定兼容比较。 |
边界条件
- 空集合
- 零长度区间
- 端点相触是否冲突
- 相同结束点
- start>end
- 闭区间与半开区间混用
错误模式
| Pattern | Why it fails / fix |
|---|
| 排序键凭直觉 | 最多兼容常按结束，合并常按开始；排序键必须匹配不变量。 |
| 端点比较差一位 | [a,b) 用 >=，闭区间可能用 >；先写区间语义。 |
| 把无权证明套到带权目标 | 交换只保持数量，不能保持不同价值的总收益。 |
| 冲突时保留更晚结束者 | 这会缩小未来空间，违反选择型不变量。 |
选择与排除规则
- 先辨别选择、合并还是覆盖，再选排序键。
- 有权重时检查 weighted interval DP。
- 代码中固定端点闭合语义。
- 在线变化时不要硬套一次性排序。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 选择 2 个；[1,2) 比 [0,3) 留出更多未来空间。 |
| Setup | 时段为 [0,3)、[1,2)、[2,5)、[4,6)。 |
| Trace | 按结束先选 [1,2)，再选 [2,5)；其余与当前边界冲突。 |
Recall prompts
我的补充