找到你要的答案

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

Q:动态规划:设计一个O(n log n)时间的算法

Please consider the following question:

There are n presentations at a conference and each has a start time and a finishing time. You cannot attend all of them because some of them overlap. Each presentations have values corresponding to your desire to attend them.

In O(n log n) time, use a dynamic programming algorithm to find a set of presentations with maximal total value such that none of their times overlap.

My thoughts:

By using dynamic programming, we would check each presentation, storing its start time, finishing time, value, one at a time (and compare if overlaps previous stored data). However, how would do this in O(n log n) time?

请考虑以下问题:

在会议上有n个演示文稿,每个都有一个开始时间和完成时间。你不能参加所有的人,因为他们中的一些重叠。每个陈述都有相应的价值观,你的愿望,参加他们。

在O(n log n)的时间,使用一个动态规划算法找到一组演示文稿的最大总价值,使他们的时间重叠。

我的思想:

通过使用动态编程,我们将检查每个演示文稿,存储其开始时间,整理时间,价值,一次一个(比较,如果重叠以前存储的数据)。然而,如何做到这一点在O(N log n)的时间?

answer1: 回答1:

Sort the interval by end time (this is O(nlogn)), then apply the DP solution that follows the recursive formulas:

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]

In the above recursive formula:

  • Finding the desired value of j is done by binary search easily (since end is sorted).
  • The argument i of the recursive function is the current "candidate" presentation.
  • The general idea is - you either attend this conference (and then cannot go to any other conference that overlap, thus recurse to D(j)) - or you don't and go on to the next candidate.
  • The maximal value possible is denoted by D(n).
  • Finding the actual presentations you went to is done after the DP solution, by tracing back your choices - if you decided to go to D(j)+values[i] in the max{} function - add i, otherwise - you don't attend it.

按结束时间排序的区间(这是O(nlogn)),然后应用如下的递推公式解法:

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]

在上述递推公式:

  • Finding the desired value of j is done by binary search easily (since end is sorted).
  • The argument i of the recursive function is the current "candidate" presentation.
  • The general idea is - you either attend this conference (and then cannot go to any other conference that overlap, thus recurse to D(j)) - or you don't and go on to the next candidate.
  • The maximal value possible is denoted by D(n).
  • Finding the actual presentations you went to is done after the DP solution, by tracing back your choices - if you decided to go to D(j)+values[i] in the max{} function - add i, otherwise - you don't attend it.
answer2: 回答2:

This can be done in O(nlgn) time as:

  1. Construct an array of start times and sort it. The end time and corresponding value for each start time can be maintained using a hash table, separate arrays with same indices for same presentation values or they can be augmented to the start time array. This operation takes O(nlgn) time.
  2. Using DP. Now we constuct an array, say array, of length n whose ith element stores the optimal value for presentations indexed i to n as in sorted start array for presentations.(1-indexed) Initialise all array elements to 0. O(n) time.
  3. Assign array[n] to value[n], value for nth presentation in start time array. O(1)
  4. Use binary search to find end_time[n-1] location in start_time array i.e. which start time index is just greater than this end time, let this index be k. Then

    Array[n-1] =max(value[n-1] + Array[k], Array[n])
    

    O(lg(n)) time for step 4.

  5. Repeat steps 3 and 4 to Array[n-1] to get Array[0] which is the optimum value that can be achieved. O(nlgn) time.

这可以在O(nlgn)时间:

  1. Construct an array of start times and sort it. The end time and corresponding value for each start time can be maintained using a hash table, separate arrays with same indices for same presentation values or they can be augmented to the start time array. This operation takes O(nlgn) time.
  2. Using DP. Now we constuct an array, say array, of length n whose ith element stores the optimal value for presentations indexed i to n as in sorted start array for presentations.(1-indexed) Initialise all array elements to 0. O(n) time.
  3. Assign array[n] to value[n], value for nth presentation in start time array. O(1)
  4. 使用二进制搜索在start_time阵列即开始时间指数是大于结束时间找到end_time [ N-1 ]的位置,让这个指数是K,然后

    Array[n-1] =max(value[n-1] + Array[k], Array[n])
    

    O(lg(n))步骤4的时间。

  5. Repeat steps 3 and 4 to Array[n-1] to get Array[0] which is the optimum value that can be achieved. O(nlgn) time.
algorithm  big-o  dynamic-programming  mergesort