简单最大利润调度算法

Simple Max Profit Scheduling Algo

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

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

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

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

对持续时间进行排序是正确答案。正如@liori 指出的那样,有多种方法可以对整数进行排序,但无论如何,您仍然需要对持续时间进行排序。

让我们看一下问题的抽象。从 L[a,b,c]D[x,y,z] 开始。假设任务按照给定的顺序执行,那么结束时间是E[a,a+b,a+b+c],所以

profit = (x - a) + (y - (a+b)) + (z - (a+b+c))

相同
profit = x + y + z - 3a - 2b - c

由此可见,截止日期的顺序并不重要,重要的是任务执行的顺序。第一个任务的持续时间从利润中减去很多次。但是最后一个任务的持续时间只会从利润中减去一次。很明显,任务需要按照从最短到最长的顺序完成。