作业调度算法"最早结束时间优先"的计数示例

Question

好吧,我们有贪婪的算法用于作业调度(调度最大作业数).我们可以使用不同的技术

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

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

这里是前三种方法的反例

最短的工作优先:

在这里,我们可以安排2个工作而不是短工作.

最早的开始时间:

在这里,我们可以安排6个较小的工作,而不是之前开始的工作

首先是最小冲突的工作:

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

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

更新1:

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

Answer 1

最早的结束时间首先是贪心算法,它为上述问题提供了最优算法.(实际上你提到的问题叫做Interval Scheduling问题)

可以使用充电参数来完成证明.您将贪心算法的输出与最优解决方案进行比较,并认为您的解决方案并不比最佳解决方案差.