01先把问题说具体
有活动 [1,4)、[2,3)、[3,5)、[5,7),只能参加互不重叠活动,最多选几个?
02一步步得到方法
为什么选最早结束,而不是最早开始
越早结束给后续留下的时间不比其他首活动少。若最优方案第一个活动为 B,而 A 是最早结束活动,把 B 换成 A,之后原来能接 B 的活动也一定能接 A,活动数不变。
确定 A 后,剩下只需在开始时间≥A.end 的活动里解决同样问题,因此可重复应用这条安全规则。这既有贪心选择性质,也有剩余子问题结构。
输入语义与目标要固定
本课活动为半开区间 [start,end),end 相同于下一活动 start 可接续,且每活动收益都算 1。若要最大总收益,最早结束可能丢掉一个很高收益的长活动,通常改用带前驱查找的加权区间 DP。
结束早保留更多未来空间
在最大化互不冲突活动数量的问题中,把最优解第一项替换成结束更早的可选活动,不会减少它后面能接的活动。重复这个交换就得到按结束时间选择的正确性。
如果每项活动价值不同,结束早只保证留下时间,不保证留下更高价值组合;这时可能需要按结束排序后的加权区间 DP。目标从数量变为收益是一个真正的算法变化。
03把一个小例子完全算清楚
活动 [1,4)、[2,3)、[3,5)、[5,7)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 按结束排序 | [2,3)、[1,4)、[3,5)、[5,7) | 结束越早越先考虑 |
| 选 [2,3) | last_end=3 | 给后续留空间 |
| 跳 [1,4),选 [3,5) | last_end=5 | 允许首尾相接 |
| 选 [5,7) | 共 3 个 | 最优 |
窄屏可左右滑动表格,阅读完整计算与理由。
按最早开始会先选 [1,4),本例只能再接 [5,7),少选一个。
04为什么这个方法成立
- 将任意最优方案首活动替换为最早结束活动,不减少后续可行集合。
- 剩余活动构成同类型问题。
- 递归地安全固定首项,最终获得最大数量。
05把推导翻译成代码
Python · 可独立运行的教学实现
def choose_intervals(intervals):
chosen, end = [], float("-inf")
for start,finish in sorted(intervals,key=lambda x:x[1]):
assert start < finish
if start >= end:
chosen.append((start,finish))
end = finish
return chosen逐个理解关键决定
key=lambda x:x[1]- 按结束时间排序,目标不是最大覆盖长度。
start >= end- 半开区间相接合法;闭区间不重叠要求可能是严格大于。
06时间、空间与实现范围
排序 O(n log n),扫描 O(n),输出与排序副本 O(n)。
允许零长度活动时需额外定义是否占用时间和同坐标顺序;本实现要求正长度。
07改变条件,检查哪里会出错
按区间最短排序
最短活动可能卡在中间,同时阻塞两侧可连续活动;没有最早结束的交换保证。
把加权收益问题当成数量问题
例如一个长活动价值很高时,选最多短活动不一定利润最高。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[1,10) 与 [2,3)、[3,4)、[4,5) 选什么?
需要一点提示
比较数量而非时长。
查看解析与答案
后三个,共 3 个。
若 [1,10) 收益 100,其余各 1 呢?
需要一点提示
目标函数变了。
查看解析与答案
应选收益 100,原贪心不适用,需加权调度算法。
如何求最少删除多少区间使不重叠?
需要一点提示
保留数量最大。
查看解析与答案
原数量减去最大可选数量,在同一端点语义下成立。