Chapter 6

In dynamic programming, we solve problems by finding a way to decompose them into subproblems that we can then use to build a solution.

In this section, we look to solve the weighted interval scheduling problem using dynamic programming. In this problem, our goal is to maximize the value of the intervals we schedule. The key to this problem is recognizing that each interval is either in the optimal solution, or it is not, so all we need to do is choose between each one. If we don't accept a job, we can check the next job. If we do accept a job, some jobs might not be compatible so we only check the next compatible job. We are looking to maximize the total value, so we make this choice based on whichever one accomplishes this. That is, if v(j) is the value of job j and p(j) is the next job compatible with job j, we can write the value of the optimal solution for jobs 1…j as Opt(j) = max( v(j) + Opt(p(j), Opt(j-1)).

This recursive algorithm to compute Opt(j) is not very efficient however. We need to use memoization to improve the run time. This technique saves the values already computed so we are not recomputing the same value repeatedly. This gives our algorithm a run time of O(n) if the intervals are sorted by finish time.

Readability: 8