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:
