Q：动态规划：设计一个O（n log n）时间的算法

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?

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.

``````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.

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 which is the optimum value that can be achieved. O(nlgn) time.

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 which is the optimum value that can be achieved. O(nlgn) time.
algorithm  big-o  dynamic-programming  mergesort