调度最多的时间间隔而不是安排最多的任务

Question

间隔调度倾向于考虑如何调度最大数量的任务，而不是尽可能多地安排时间。对于如何修改典型的贪婪算法以优化时间使用而不是任务的#，有什么想法吗？

Answer 1

下面是一个O(nlog n)动态规划算法：

假设有n个任务，从时间b(j)开始，以1 <= j <= n的时间e(j)结束。设f (x )是调度(使用)的最大时间，约束条件是没有调度任务使用任何时间x. (x不一定是整数)。我们将计算f(max(e(J)，其中最大值将用于所有任务:这将是最后的答案。

我们不会在数组中记录f()的值，这样f(x)由数组的xth元素给出，我们只记录一个对数组(x，y)，按x的顺序递增，但允许x值中的间隙。调用这个数组S。在S中将有一个(x，y)对，对于每一个最佳(“最充分”)解，其上一次使用的时间间隔正好结束于时间x，并且总共使用y个时间单位。为了找到f(x)，我们将在这个对数组中进行二进制搜索，以找到具有x‘<= x但尽可能大的对对(x'，y)。直观地说，这意味着在寻找不需要时间的最佳解决方案时，如果没有使用时间的最佳解决方案，直到“time x”，那么我们“退回”到之前的最佳解决方案。

1. 按结束时间对所有n个任务进行排序。
2. 对于j从1到n：
   • 想法:尝试将任务j添加到能够容纳它的最佳时间表中，即f(b(j))。我们将把这个时间表与f(e(j))进行比较，看看是否最好包括任务j。计算f(b(j))需要通过S进行二进制搜索，但f(e(j))可以在恒定时间内计算，因为它总是S中最右边的一对。
   • 如果f( b(j) ) + e(j) -b(J)> f( e(j) )，则移除S中的任何尾随对(e(j)，y)并附加(e(j)，f(b(j)) +e(J)- b(j))到S。

​

1. 返回S的最后一个元素，它对应于f(max(e(J)。

要实际恢复调度，可以向数组S中的每个对添加第三个元素，以记录刚刚添加的最右边任务的标识。然后，一旦上面的算法运行完毕，只需从结束时，在每一步二进制开始，通过数组S进行追溯--寻找在b(j)或之前结束的最完整的解决方案，其中j是上一步中报告的任务。