algorithm - 简单最大利润调度算法

Question

假设您有一个持续时间数组 L[5,8,2]，截止日期为 D[13,8,7]。如果您有每个事件的结束时间 E[i]。对于每项事件，您收到(或损失)金额 D[i] - E[i]，总计获得或损失的总金额，在本例中为 4。E 取决于顺序你做每项事件。例如，如果您按升序执行每个 L[i]，您得到的 E 将是 [7,15,2]。

我发现最大值出现在您对 L 数组进行排序之后，它的运行时间为 O(nlog n)。令人着迷的是，在对 L 数组进行排序后，无需对 D 数组 b/c 进行排序，对于任何排列，您最终都会得到相同的最大值截止日期(我试过更大的集合)。有没有更好的方法来解决这个问题，让运行时间小于O(nlogn)？我花了几个小时尝试对长度和截止日期进行各种线性调整，但无济于事，甚至使用条件语句。在我看来，这可以在 O(n) 时间内完成，但我一辈子都找不到。

Answer 1

您对无限整数数组进行排序。对整数进行排序的方法比仅比较大小的方法更快:确定性情况的 O(n log log n) 和随机算法的 O(n sqrt(log log n))。参见 https://cstheory.stackexchange.com/a/19089进行更多讨论。

如果整数是有界的(比如，你可以保证它们不会大于某个值)，counting sort将在 O(n) 中解决问题。