跳转至

贪心的适用条件:安排尽量多的区间

同样能先选,为什么优先选结束早的?

用 [开始,结束) 记一项活动。例如 [1,2) 从 1 开始,到 2 时已经结束,允许另一项在 2 接上。现有活动 A [0,4)、B [1,2)、C [2,3)、D [3,4)。选开始最早的 A 就占了整段;选最早结束的 B,还能接 C 和 D。每次比较的是能留给未来的时间,而不是本项什么时候开始。

B、C 的边界都在 2,为什么可以接起来?

我们用左闭右开的区间,B 在时刻 2 已结束。若题目把端点也算作冲突,就需要修改兼容条件。

先修:排序、贪心算法。

读完能做:下面会试着从一份最优计划里换掉第一项,看它还能不能容下同样多的活动。这种证明叫**交换论证**。再改一个条件,也可以检验这条挑选规则能不能继续用。

假设一台机器一次只能运行一个任务。每项任务有固定起止时刻,沿用开头的记法,一个任务结束的时刻可以立刻启动下一项。若目标是完成尽量多的任务,先选**结束最早**的可用任务,再做同样的选择。

任务 A 占用 [0, 8),B 占用 [1, 3),C 占用 [3, 5),D 占用 [5, 7)。若按开始时间选,先取 A,只能做一项。按结束时间选择 B、C、D 能做三项。

为什么结束最早可以推广?取一份最优安排,把它第一个区间换成结束最早的区间。替换后,后续区间还都能放下,任务数也相同。剩余问题又是同一种选择。实现时先按结束时间排序,再扫一次,时间 \(O(n\log n)\)。

改一个条件

若 A 价值 100,其余每项价值 1,目标变成价值最大时,B、C、D 只有 3。此时可以用动态规划:把区间按结束时刻排好,比较「跳过当前项」和「选它并接上最后一个兼容区间之前的最优值」。

自测

你要最早完成一个任务,和你要完成尽量多任务,目标有何不同?如果任务可以让出机器后再继续,原模型哪条假设失效?

参考思路

第一个只需找结束最早的一项;第二个还需考虑后续可兼容项。允许中断和恢复时,任务不再必须连续占用固定区间,状态与调度策略都要重建。