algorithm - 作业调度算法的反例 "Earliest End time First"

Question

好吧，我们有作业调度的贪心算法(调度最大数量的作业)。我们可以使用不同的技术

1. 最短的工作优先
2. 最早开始时间优先
3. 首先是冲突最小的工作
4. 最早结束时间优先

我有前三个策略的反例，但找不到第四个策略的反例。

这里是前三种方法的反例

最短作业优先:

在这里我们可以安排 2 个作业而不是一个较短的作业。

最早开始时间优先:

在这里，我们可以安排 6 个较小的作业，这些作业稍后开始，而不是安排在一个较早开始的作业上

冲突最小的作业优先:

在这里我们可以安排 4 个冲突为 3,4,4,3 的作业，而不是 3 个冲突最小的作业，即 2,3,3

那么，最后一个最早结束时间优先的反例是什么？我找不到这个的反例。那么，它总是为每组数据给出一个最优解？

更新 1:

我有一个执行者来执行作业，我想执行最大数量的作业。

Answer 1

Earliest End time First 是贪心算法，为上述问题给出最优算法。 (其实你说的这个问题叫Interval Scheduling问题)

证明可以使用 charging argument 完成.您将贪婪算法的输出与最优解进行比较，并争辩说您的解并不比最优解差。