作业调度变体

Question

我正在尝试解决间隔调度问题的一个变体:给定一组n个作业，每个作业需要1个处理单元才能完成，并且每个作业都有一个可用的间隔(可以执行的开始时间和结束时间)，找出可以调度的最大作业数。

我尝试的解决方案是对作业进行排序，并始终选择可用性结束时间最早的作业，同时在每次迭代后删除不可用的作业。

while jobs are not empty:
    remove jobs that are not available
    find the job with earliest end_availability_time
    execute the job

我使用优先级队列，在该队列中，我在开头插入所有作业，而不是排序。此解决方案的时间复杂度为O(nlogn) (每个作业插入优先级队列一次，并从优先级队列中弹出一次)。

有没有解决这个问题的最佳方法？

Answer 1

您可以将其视为assignment problem的一个实例。您只需在一个单元的插槽中转换时间间隔，并将每个作业连接到它可以在其中执行的每个单位时间间隔。

解决此问题的一种可能算法是Hungarian algorithm，或者您可以将其编码为maximum flow问题并使用Ford-Fulkerson algorithm解决它。

编辑多想一想，你的解决方案也是最优的。下面是证明的草图:设A是贪婪算法找到的最优解，B是不同的最优解。考虑一个作业j是在B中调度的，但不是在A中调度的。这意味着贪婪算法从可用作业列表中删除了j，只有当它在j的可用性间隔中的每个时间段都调度另一个作业时，才会发生这种情况。那么，这些作业中的一个不能在B中，因为它将在j的同一时间调度。因此，这意味着A和B具有相同数量的作业。

换句话说，贪心算法在每个时间段调度一个作业，所以它必须是最优的。