贪心
01 / 共享的机制
每一步取局部最优,并能证明这次提交后续不会被推翻。 没有回溯、没有 DP 表:要么用交换论证说明换掉任意一次贪心都不会更优, 要么用领先论证说明贪心在每个前缀上都不落后。 三个经典子模式把这个想法落成算法:对区间排序后取、在数组上扫描追踪可达边界, 以及在累积量上「一旦失败立即重置起点」。
01 / 一句话本质
把区间按终点排序,然后从左到右扫一遍, 每个起点不小于上一个已选终点的区间就拿下。 交换论证保证:取最早结束的那个永远安全 —— 换成别的只会一样好或更差。
题目最多不重叠区间数输入[1,3] [2,5] [3,6] [5,9] [8,12]
输入有 5 个区间,按给定顺序。贪心思路:按终点排序后,扫一遍,每个起点不小于已选终点的就拿。
步
0 / 12
已选
—
上次终点
−∞
0 / 12
02 / 模式骨架
# 按终点排序 —— 不是起点intervals.sort(key=lambda iv: iv.e)result ← []; lastEnd ← −∞for iv in intervals:if iv.s ≥ lastEnd:result.push(iv) # 取lastEnd ← iv.eelse:# 跳过 —— 会和上一个已选冲突# |result| 即为最大不重叠区间数
03 / 什么时候用这个模式
"最多互不重叠的区间数"
最教科书式的触发词。会议安排、教室预定、活动选择 —— 只要问题是最多能选多少个不重叠的区间。 按终点排序后贪心地取就完事。
"至少移除多少使其不重叠"
LC 435 的说法。其实是同一个问题的反面:保留的最多 = 最大不重叠数,所以移除数 =
N − 保留数。 按终点排序的贪心一次就能给出两边的答案。"用最少飞镖戳爆气球"
LC 452。每个气球是一段闭区间,在 x 射出的箭会戳爆所有覆盖 x 的气球。 答案就是最少分组数 —— 等价于从另一边数最大不重叠数。
"带权区间调度"
听着相似但本质不同 —— 区间一旦带上权重、目标是总价值最大,贪心就会出错。 这种题变成按终点排序的区间 DP,需要前驱查找(LC 1235)。
04 / 常见坑
i.
按起点而非终点排序。
最常见的 bug。按起点排序在简单不重叠输入上能跑,但只要前面有一条长区间就会出错 —— 一旦把它选进来,后面好几条短区间都被堵死。按终点排序时,局部最便宜的选择正好也是全局最稳的选择。
ii.
边界上的严格
> 还是非严格 ≥。[1, 5] 接 [5, 8] 算不算重叠?闭区间(LC 452 的气球)中端点相接算重叠 —— 用严格 >;半开区间(10:00 结束的会议不挡 10:00 开始的)用 ≥。 骨架相同,比较符相反。iii.
跟「区间合并」混淆。
区间合并按起点排序,把重叠并入输出区间; 区间调度按终点排序,数最多能塞多少个不重叠。 外形相似,问题不同:一个求并集,一个求最大不重叠子集。
05 / 去 LeetCode 上练习
四道题,大致按难度排序。最难的 LC 1235 是反例:加上权重以后贪心就崩了,实际上是 DP。
— / 什么时候用哪个
区间调度
输入是一组区间、问「最多挑出多少个互不重叠」时用。按终点排序后, 每个起点超过已选区间终点的区间就拿。交换论证保证「最早结束」永远安全。
按终点排序 · LC 435 · LC 452
跳跃游戏
每个元素决定你能从这里移动多远时使用。从左到右扫描,维护当前能到达的最远下标; 一旦扫描位置超过这个边界,终点就不可达。
追踪最远 · LC 55 · LC 45
加油站
一段(环形或线性)路径上,某个累积量必须始终非负时用。 一旦运行总和跌破零就把起点重置到下一格 —— 任何使其失败的段都不会是合法起点。
失败即重置 · LC 134 · LC 53