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

Question

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?

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

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