This is an old revision of the document!
Table of Contents
Chapter 6 - Dynamic Programming
Section 6.1 - Weighted Interval Scheduling: A Recursive Procedure
The section begins by outlining the problem which we are seeking to solve. It is the same interval scheduling problem from earlier in the text, except now, the intervals have weights assigned to them and we want to maximize the total weight.
The section then outlines a recursive structure for solving this problem. We first consider the final job: either that job is in the optimal solution, or that job is not in the optimal solution. Therefore, if there are j jobs, Opt(j) = max (value(j) + Opt(p(j)),Opt(j-1)), where p(j) is the first available job behind the start time of job j. And this leads directly into the algorithm for computing the optimal solution. If j == 0, we Return 0, otherwise, we return max (value(j) + Opt(p(j)),Opt(j-1)). And note that, within this algorithm we are computing the optimal solution for each j = 1,2,…, n.
If we just run the algorithm as is, then it would run in polynomial time, having to run through the same recursions over and over. But we have a strategy for combatting this: memoization. We simply keep track of the previously-calculated values, and this way, the runtime is reduced to O(n) if we assume that the input intervals are sorted by their finish times. The section proceeds to walk through a clear example of how to output a solution from the algorithm, that is, the exact jobs scheduled while maintaining linear time.
I found this section intuitive and straight-forward. I had also grasped the material very well from the class when this was covered. I would rate the readability at 9/10.
