Chapter 6

• In general, most problems do not have a natural greedy algorithm solution that works
• Divide and conquer is often not strong enough to reduce exponential brute-force search down to polynomial time
• Dynamic Programming: one implicitly explores the space of all possible solutions, by decomposing things into a series of subproblems, and then building up correct solutions to larger and larger subproblems

• Each interval has a certain value (or weight), and we want to accept a set of maximum value.

Designing a Recursive Algorithm

• n requests (1,…,n)
• each request i specifies a start time si and finish time fi.
• each request i also has a value or weight (vi)
• compatible intervals: do not overlap
• goal: select a subset of mutually compatible intervals so as to maximize the sum of the values of the selected intervals
• sort requests in order of nondecreasing finish time
• define p(j), for an interval j, to be the largest index i<j such that intervals i and j are disjoint
  • leftmost interval that ends before j begins
• p(j) = 0, if no request i<j is disjoint from j
• Optimal solution O: either interval n belongs to O or it doesn't
  • if it is, no intervals indexed between p(n) and n can belong to O