作业调度变化

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的实例。您只需要转换一个单元的插槽中的间隔，并将每个作业连接到可以在其中执行的每个单元时间间隔即可。