3. 贪心算法入门：贪心策略核心思想、最早截止时间优先（EDD）、最短处理时间优先（SPT）
大家好，欢迎来到调度算法的第三讲。今天咱们聊聊贪心算法。
说实话，我第一次接触贪心算法时，觉得这玩意儿太「鸡贼」了。每次只盯着眼前最好的选择，不管以后会怎样。但后来我发现，在调度领域，这种「短视」反而特别管用。你想想看，调度问题本质上就是一堆任务排队，你总得决定先干哪个后干哪个。贪心策略就是告诉你：别想太多，选当前最优的那个就行。
3.1 贪心策略的核心思想
贪心算法的核心，说白了就八个字：局部最优，全局最优。
什么意思呢？就是每一步都选当前看起来最好的方案，最终得到的结果就是全局最优解。当然，这需要问题本身满足「贪心选择性质」和「最优子结构性质」。不过咱们做工程的不需要纠结这些数学定义，你只要记住：能用贪心解决的问题，往往都有某种「排序」的规律。
我个人习惯把贪心算法分成三步走：
- 确定贪心策略 —— 按什么规则选？比如按截止时间、按处理时间、按优先级。
- 排序 —— 把任务按这个规则排好序。
- 依次处理 —— 按排序后的顺序一个一个处理。
就这么简单。但难点在于第一步——选对策略。选错了，结果可能差十万八千里。
核心要点：贪心算法不是「瞎选」，而是基于某种明确的优先级规则。这个规则必须能保证局部最优能导向全局最优。
3.2 最早截止时间优先（EDD）
EDD，全称 Earliest Due Date。顾名思义，就是谁先到期，谁先做。
这个策略在单机调度中非常经典。我曾在某制造企业的排产系统里用过它，效果出奇的好。当时有个车间，每天要处理上百个订单，每个订单都有交货期。工人问我：「这么多活，先干哪个？」我说：「哪个最急就先干哪个。」这就是EDD。
EDD 的目标是最小化最大延迟。什么意思？就是让所有任务中，最晚的那个延迟尽可能小。用数学语言说，就是最小化 max(L_i)，其中 L_i = C_i - d_i（完成时间减去截止时间）。
来看个例子：
| 任务 | 处理时间 p_i | 截止时间 d_i |
|---|---|---|
| A | 3 | 5 |
| B | 5 | 10 |
| C | 2 | 4 |
| D | 4 | 8 |
按 EDD 排序：C（d=4）→ A（d=5）→ D（d=8）→ B（d=10）。
计算一下完成时间和延迟：
- C：完成时间 = 2，延迟 = 2 - 4 = -2（提前完成）
- A：完成时间 = 2+3=5，延迟 = 5 - 5 = 0
- D：完成时间 = 5+4=9，延迟 = 9 - 8 = 1
- B：完成时间 = 9+5=14，延迟 = 14 - 10 = 4
最大延迟是 4。如果你换一种顺序试试，比如按处理时间排，最大延迟可能会更大。
小技巧：EDD 在截止时间比较宽松时效果很好。但如果截止时间很紧，任务容易扎堆到期，这时候 EDD 可能会让短任务被长任务堵住。我曾经遇到过这种情况，后来加了个「优先级权重」才解决。
3.3 最短处理时间优先（SPT）
SPT，全称 Shortest Processing Time。这个更简单——谁干得快，谁先干。
SPT 的目标是最小化平均完成时间。为什么？因为短任务先做，后面的任务就不用等太久。你想想看，如果有个长任务占了机器 10 个小时，后面 10 个短任务每个都要等 10 小时，平均完成时间就很高。反过来，短任务先做，平均等待时间就降下来了。
还是刚才那个例子，按 SPT 排序：
| 任务 | 处理时间 p_i | 截止时间 d_i |
|---|---|---|
| C | 2 | 4 |
| A | 3 | 5 |
| D | 4 | 8 |
| B | 5 | 10 |
排序结果和 EDD 一样？嗯，这次是巧合。但 SPT 的排序依据是处理时间，不是截止时间。
计算平均完成时间：
- C：完成时间 = 2
- A：完成时间 = 5
- D：完成时间 = 9
- B：完成时间 = 14
平均完成时间 = (2+5+9+14)/4 = 7.5。
如果你把长任务 B 放最前面，平均完成时间会变成 (5+8+12+14)/4 = 9.75。看到了吧？SPT 确实能降低平均完成时间。
注意：SPT 虽然能降低平均完成时间，但它完全不管截止时间。如果有个长任务截止时间很紧，按 SPT 排可能会让它严重超期。我曾经在一个项目中吃过这个亏，后来改用了 EDD 和 SPT 的混合策略。
3.4 EDD vs SPT：怎么选？
这两个策略各有千秋。我画了一张图，帮你快速理解它们的区别：
3.5 避坑指南
最后，分享几个我踩过的坑：
- 不要盲目用 EDD —— 如果所有任务的截止时间都差不多，EDD 就退化成随机排序了。这时候 SPT 可能更好。
- SPT 不是万能的 —— 它只关心平均完成时间，不关心单个任务的延迟。如果你的客户有严格的交货期，SPT 可能会让你得罪大客户。
- 动态环境要小心 —— 任务不是一次性到达的，而是陆续来的。这时候静态排序就不够用了，需要动态调整。我后来在项目中引入了「滚动窗口」机制，每来一批新任务就重新排序一次。
一句话总结：EDD 保底线（不让任何任务超期太多），SPT 提效率（让整体完成时间最短）。实际项目中，我经常把两者结合——先用 EDD 筛选出紧急任务，再用 SPT 在紧急任务内部排序。
好了，这一讲就到这里。贪心算法看似简单，但用好了威力无穷。下一讲我们会聊聊更复杂的调度策略，到时候你会发现，很多高级算法其实都是在贪心的基础上加了「后悔药」机制。
公众号:蓝海资料掘金营，微信deep3321