algorithm - 动态规划 : design an algorithm that is in O(n log n) time

Question

请考虑以下问题:

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

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

我的想法:

通过使用动态规划，我们将检查每个演示文稿，存储其开始时间、结束时间、值，一次一个(并比较是否与先前存储的数据重叠)。但是，如何在 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是当前“候选”表示。
• 一般的想法是 - 你要么参加这个 session (然后不能去任何其他重叠的 session ，因此递归到 D(j)) - 或者你不参加并继续下一位候选人。
• 可能的最大值用D(n)表示。
• 在 DP 解决方案之后，通过追溯您的选择，找到您去过的实际演示文稿 - 如果您决定前往 中的 D(j)+values[i] max{} 函数 - 添加 i，否则 - 你不参加它。