我试图理解贪婪算法调度问题是如何工作的。
所以我已经阅读和搜索了一段时间，因为我不能理解贪婪算法调度问题。
我们在一个资源上有N个作业要调度。作业（i）具有请求的开始时间s（i）和结束时间f（i）。
我们选择了一些贪婪的想法…
按s的递增顺序接受（“最早开始时间”）
按F-S的递增顺序接受（“最短工作时间”）
按冲突数量的递增顺序接受（“最少冲突”）
按F的递增顺序接受（“最早完成时间”）
书上说，最后一个，按f的递增顺序接受，总会给出一个最优解。
但是它没有提到为什么它总是给出最优解，为什么其他3个不给出最优解。
他们提供的数字说明了为什么其他三个方案不能提供最佳解决方案，但我不明白这意味着什么。
因为我的名声不好，所以我不能张贴任何图片，所以我会尽量画出来。
|---||---||---|
|—————————————————————---|
s的递增阶
低估的解决方案
|-----------| |-----------|
|———-|
f-s级数
低估的解决方案
|———————————————————————————|
|—————————————————————————-|
|—————————————-|
|—————————————-|
冲突数量的递增顺序。
低估的解决方案
这就是它的样子，我不明白为什么这是每个场景的反例。
如果有人能解释为什么每一个贪婪的想法都不起作用，那将非常有帮助。
谢谢您。
最佳答案
由于@vish4071已经解释了为什么选择最早的完成时间将导致最佳解决方案，所以我只解释反例。任务开始于[a,b]结束于a。我将使用你提供的反例。
最早开始时间
假设任务b，[1,10]，[2,3]，[4,5]最早的开始时间策略将选择[6,7]，然后拒绝其他3个，因为它们都与第一个策略冲突。然而，我们可以看到，[1,10]是最优解，因此最早开始时间策略并不总是产生最优结果。
最短执行时间
假设任务[2,3], [4,5], [6,7]，[1,10]，[11,20]这种策略会选择[9,12]，然后拒绝另外两个，但最佳解决方案是[9,12]，[1,10]因此，最短执行时间策略并不总是会产生最佳结果。
最小碰撞量
这个策略看起来很有前途，但是你的11个任务的例子证明它不是最优的假设任务：[11,20]，3x[1,4]，[3,6]，[5,8]，[7,10]，3x[9,12]和[11,14]。[13, 16]与其他任务只有2个冲突，这比任何其他任务都少，因此它将首先通过最少的冲突策略进行选择。然后将选择[7,10]和[1,4]，并拒绝所有其他任务，因为它们与已选择的任务冲突。即3个任务，但是可以选择4个任务而不发生冲突：[13, 16]、[1,4]、[5,8]和[9,12]。
您还可以看到，在这些示例中，最早完成时间策略将始终选择最佳解决方案。注意，一个以上的最优解可以存在相同数量的选定任务。在这种情况下，最早完成时间策略将始终选择其中之一。
关于algorithm - 贪婪算法，调度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32394987/