简单最大利润调度算法
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
由此可见，截止日期的顺序并不重要，重要的是任务执行的顺序。第一个任务的持续时间从利润中减去很多次。但是最后一个任务的持续时间只会从利润中减去一次。很明显，任务需要按照从最短到最长的顺序完成。
假设您有一个持续时间数组 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
由此可见，截止日期的顺序并不重要，重要的是任务执行的顺序。第一个任务的持续时间从利润中减去很多次。但是最后一个任务的持续时间只会从利润中减去一次。很明显，任务需要按照从最短到最长的顺序完成。