作业调度算法“最早结束时间优先”的反例

Question

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

1. 最短的作业优先
2. 最早开始时间在先
3. 首先将冲突降至最低的作业
4. 最早的结束时间在前

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

以下是前三种方法的反例

最短的作业优先:

最早开始时间：

首先是冲突最小的工作：

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

那么，最后一个最早的结束时间的反例是什么 首先我找不到反例。那么，它总是为每组数据提供最佳解决方案吗？

更新 1 ：

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

Answer 1

最早结束时间优先的贪婪算法给出了上述问题的最优算法。(实际上你提到的问题叫做区间调度问题)

可以使用收费论点进行证明。你将贪婪算法的输出与最优解进行比较，并认为你的解并不比最优解差。