01先把问题说具体
若任务耗时为 [3,1,2],所有任务同时到达且不可抢占,怎样安排顺序让总等待时间最小?
02一步步得到方法
贪心先作出不可撤回的选择
尝试每次先执行耗时最短的任务。直觉是短任务先走能让更多人较早开始,但直觉不是证明。我们需要说明:任何最优顺序都能调整成这个选择而不变差。
比较相邻两项 a、b,前面已经等待 T。先 a 后 b,两项等待为 T 与 T+a;换成 b 后 a,为 T 与 T+b。后面任务等待的总 a+b 不变,所以当 a>b 时交换会减少总等待 a−b。
把局部交换推广到全局
只要还有较长任务排在较短任务前,就可以通过相邻交换减少或不增加成本。反复交换最终得到耗时升序,因此存在按升序的最优解。这是交换论证,不是仅靠跑几个例子。
贪心规则依赖目标函数和输入条件。若任务有不同到达时间、截止期限或权重,刚才的相邻比较式可能改变;不能把短的先做用于所有调度问题。
局部规则需要一条全局桥梁
设计贪心时先问:为什么存在某个最优解愿意采用我的第一步?交换论证常从任意最优解出发,把它的某个选择替换成贪心选择,并证明可行且不更差。
完成第一步后还要说明剩余问题仍具有相同结构,才能递归使用相同规则。几个小例子成功只能帮助发现候选规则,不能替代覆盖所有合法输入的论证。
03把一个小例子完全算清楚
任务耗时 [3,1,2]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 原顺序 | 等待 0、3、4,总和 7 | 先做长任务 |
| 交换成 [1,3,2] | 等待 0、1、4,总和 5 | 减少 2 |
| 升序 [1,2,3] | 等待 0、1、3,总和 4 | 消除全部逆序 |
窄屏可左右滑动表格,阅读完整计算与理由。
正确贪心的核心是一条可重复使用的安全选择理由。
04为什么这个方法成立
- 相邻逆序 a>b 交换后,两任务等待总和减少 a−b,其他任务不受影响。
- 任何非升序排列都可通过交换消除逆序。
- 最终升序成本不大于任意初始顺序,因此最优。
05把推导翻译成代码
Python · 可独立运行的教学实现
def minimum_waiting(durations):
assert all(x >= 0 for x in durations)
elapsed = total = 0
for duration in sorted(durations):
total += elapsed
elapsed += duration
return total逐个理解关键决定
total += elapsed- 等待时间是任务开始前已经过去的时间,不包含自身处理时间。
sorted(durations)- 规则只在本课同时到达、相同权重的条件下已证明。
06时间、空间与实现范围
排序 O(n log n),扫描 O(n),排序副本 O(n)。
贪心可能比 DP 状态少,但必须存在安全选择证明;不是所有最优问题都能如此简化。
07改变条件,检查哪里会出错
挑几个样本都正确就算证明
需要覆盖任意合法输入的交换、不变量或割性质论证。
换了目标函数仍沿用旧排序键
最大数量、最大收益和最小等待可能需要不同规则,旧证明不一定继续成立。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[2,2,2] 总等待多少?
需要一点提示
前缀和。
查看解析与答案
0+2+4=6,等长任务顺序不影响。
任务有优先级权重时仍只按耗时吗?
需要一点提示
交换后的目标差是否相同?
查看解析与答案
不一定,权重改变等待成本;可重新推导按耗时与权重比值的规则,但不能直接沿用。
如何快速否定一个可疑贪心?
需要一点提示
构造局部收益与未来冲突。
查看解析与答案
找一个小输入,让当前最优选择阻塞多个更好组合;硬币 [1,3,4]、金额 6 就能否定总选最大面值。