Chapter 6

Sometimes greedy algorithms do not provide fully correct solutions to a problem that we may be trying to solve. We are forced to resort to other approaches to designing algorithms–one such approach is dynamic programming. In dynamic programming, one implicitly explores the space of all possible solutions, by carefully decomposing things into a series of subproblems, and then building up correct solutions to larger and larger subproblems. We can think of dynamic programming as somewhat of a balance between brute force search and the divide and conquer approach.

We have seen a greedy algorithm that produces an optimal solution to the Interval Scheduling Problem, where the goal is to accept as large a set of nonoverlapping intervals as possible. The Weighted Interval Scheduling Problem is a strictly more general version, in which each interval has a certain value (or weight), and we want to accept a set of maximum value. However, the greedy algorithm that worked before (repeatedly choosing the interval that ends earliest) is no longer optimal in this more general setting.

We have n requests labelled 1, …, n, with each request i specifying a start time s_i and a finish time f_i. Each interval i now also has a value, or weight v_i. Two intervals are compatible if they do not overlap. The goal of our current problem is to select a subset of mutually compatible intervals, so as to maximize the sum of the values of the selected intervals. Let’s suppose that the requests are sorted in order of nondecreasing finish time. We’ll say a request i comes before a request j if i < j. We define p(j), for an interval j, to be the largest index i < j such that intervals i and j are disjoint (note: p(j) = 0 if no request i < j is disjoint from j).

Now, consider an optimal solution O to this problem. We can say, with certainty, that the interval n (the last one) either belongs to O, or it doesn't. If n belongs to O, then clearly no interval indexed strictly between p(n) and n can belong to O. On the other hand, if n does not belong to O, then O is simply the optimal solution to the problem consisting of the requests {1, …, n-1}.

Thus, for any value of j between 1 and n, let O_j denote the optimal solution to the problem consisting of the requests {1, …, j}, and let OPT(j) denote the value of the solution. Based on our reasoning earlier, we can say that:

OPT(j) = max(v_j + OPT(p(j)), OPT(j - 1))

As such, a request j belongs to an optimal solution to the set {1, 2, …, j} if and only if V_j + OPT(p(j)) ≥ OPT(j - 1).