algorithm - 调度最多的间隔而不是调度最多的任务

Question

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

Answer 1

这是一个 O(nlog n) 的动态规划算法:

假设有 n 个任务，从时间 b(j) 开始到时间 e(j) 结束，其中 1 <= j <= n。设 f(x) 是可以安排(使用)的最大时间量在没有计划任务使用时间 x 之后的任何时间的约束下。(x 不必是整数。)我们将计算f(max(e(j)))，其中最大值接管所有任务:这将是最终答案。

我们不会在数组中记录 f() 的值以便 f(x) 由数组的第 x 个元素给出，我们将只记录一个数组对 (x, y)，按 x 的递增顺序，但允许 x 值存在间隙。将此数组称为 S。对于每个最佳(“最完整”)解决方案，S 中将有一个(x，y)对，其最后使用的时间间隔正好在时间 x 结束，并使用 y 个单位总时间。为了找到 f(x)，我们将在这个对数组中进行二进制搜索，以找到 x' <= x 但尽可能大的对 (x', y)。直观地，这意味着当寻找在 x 之后不使用时间的最佳解决方案时，如果没有使用时间“一直到”时间 x 的最佳解决方案，那么我们将“回退”到在此之前结束的最佳解决方案。

1. 按结束时间对所有 n 个任务进行排序。
2. 对于从 1 到 n 的 j:
   • 想法:尝试将任务 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.
3. 返回S的最后一个元素，对应f(max(e(j)))。

要实际恢复计划，可以将第三个元素添加到数组 S 中的每一对，以记录刚添加的最右边任务的标识。然后，一旦上面的算法运行完毕，只需从末尾开始追溯数组 S，在每个步骤中二进制搜索结束于 b(j) 或之前的最完整解决方案，其中 j 是上一步中报告的任务.