动态规划：设计一个在 O(n log n) 时间内的算法

Question

请考虑以下问题：

会议上有 n 个演示文稿，每个演示文稿都有开始时间和结束时间。你不能参加所有这些，因为其中一些重叠。每个演示文稿都有与您参加它们的愿望相对应的价值。

在 O(n log n) 时间内，使用动态规划算法找到一组具有最大总价值的演示文稿，使得它们的 none 时间重叠。

我的想法：

通过使用动态规划，我们将检查每个演示文稿，存储其开始时间、结束时间、值，一次一个（并比较是否与先前存储的数据重叠）。但是，如何在 O(n log n) 时间内做到这一点？

Answer 1

按结束时间对间隔进行排序（这是O(nlogn)），然后应用遵循递归公式的DP解决方案：

Let start[1,...,n] be an array containing start times
Let end[1,....,n] be an array containing end times
Let values[1,...,n] be an array containing values of each presentations
Assume arrays are already sorted, such that the `i`th element in all arrays refer to the same presentation, and the array end is in ascending order.


    D(0) = 0
    D(i) = max { D(i-1), D(j) + values[i] } where j is the highest index such that end[j] <= end[i]

在上面的递推公式中：

通过二进制搜索很容易找到 j 的所需值（因为 end 已排序）。
递归函数的参数i是当前"candidate"表示。
一般的想法是 - 你要么参加这个会议（然后不能去任何其他重叠的会议，因此递归到 D(j)） - 或者你不参加并继续下一个候选人。
可能的最大值用 D(n) 表示。
在 DP 解决方案之后找到您去过的实际演示文稿，通过追溯您的选择 - 如果您决定在 max{} 函数中前往 D(j)+values[i] - 添加 i，否则 - 你不参加。

Answer 2

这可以在 O(nlgn) 时间内完成：

构造一个开始时间数组并排序。结束时间和每个开始时间的对应值可以使用散列 table 来维护，对于相同的呈现值具有相同索引的单独数组，或者它们可以扩充到开始时间数组。此操作需要 O(nlgn) 时间。
使用DP。现在我们构造一个长度为 n 的数组，比如说数组，它的第 i 个元素存储索引为 i 到 n 的演示文稿的最佳值，就像演示文稿的排序起始数组一样。（1-索引）将所有数组元素初始化为 0。O(n) 时间.
将 array[n] 分配给 value[n]，开始时间数组中第 n 个呈现的值。 O(1)
使用二进制搜索在start_time数组中找到end_time[n-1]个位置即哪个开始时间索引刚好大于这个结束时间，让这个索引k.那么
```
Array[n-1] =max(value[n-1] + Array[k], Array[n])
```
O(lg(n)) 步骤 4 的时间。
对Array[n-1]重复步骤3和4，得到Array[0]，这是可以达到的最优值。 O(nlgn) 时间。

动态规划：设计一个在 O(n log n) 时间内的算法

Dynamic programming: design an algorithm that is in O(n log n) time

algorithm

big-o

mergesort

dynamic-programming