作业调度算法的反例 "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来完成。您将贪婪算法的输出与最优解进行比较，并认为您的解并不比最优解差。