This is an old revision of the document!
Table of Contents
Chapter 6
6.1 Weighted Interval Scheduling
The problem is similar to our previous Interval Scheduling problem with the added case that jobs now have different weights; thus, no greedy algorithm can be used to solve this problem, so we must switch to dynamic programming. More specifically, we use a recursive algorithm. The algorithm relies on a simple observation: for any job j, we wither pick j or we do not pick j. This observation helps formulate the recursive case:
Compute-Opt(j):
if j = 0
return 0
elif M[j] is not empty
return M[j]
else
M[j] = max(vj + Compute-Opt(p(j)), Compute-Opt(j-1))
In the recursive case, we take the maximum of the solution containing j and the solution not containing j (picking job j or not picking job j). The runtime of this algorithm is O(n) since it makes use of memoization. Computed values are stored in array M and recalled when needed, eliminating redundant computations. Lastly, we construct a second algorithm that returns the actual set of jobs that Compute-Opt would choose since Compute-Opt only returns the value of the optimal solution. This algorithm also runs in O(n) time. The readability of this section is 8/10.
