Source code online books for professionals by professionals

Figure 7-4.  A set of random intervals where at most four mutually compatible intervals (for example, a, c, e and g) can 
be found
There are two obvious candidates for greedy selection here: If we go from left to right on the timeline, we might 
want to start with either the interval that starts first or the one that ends first, eliminating any other overlapping 
intervals. I hope it is clear that the first alternative can’t work (Exercise 7-18), which leaves us to show that the other 
one does work.
The algorithm is (roughly) as follows:
 
1.  Include the interval with the lowest finish time in the solution.
 
2.  Remove all of the remaining intervals that overlap with the one from step 1.
 
3.  Any remaining intervals? Go to step 1.
Running this algorithm on the interval set in Figure 
7-4
 results in the highlighted set of intervals (a, c, e and g).  
The resulting solution is clearly valid; that is, there aren’t any overlapping intervals in it. This will be the case in 
general; we need show only that it’s optimal, that is, that we have as many intervals as possible. Let’s try to apply the 
idea of staying ahead.
Let’s say our intervals are, in the order in which they were added, i
1
 … i
k
, and that the hypothetical, optimal 
solution gives the intervals j
1
 … j
m
. We want to show that k = m. Assume that the optimal intervals are sorted by 
finishing (and starting) times.
15
 To show that our algorithm stays ahead of the optimal one, we need to show that for 
any r £ k, the finish time of i
r
 is at least as early as that of j
r
, and we can prove this by induction.
For r = 1, it is obviously correct: The greedy algorithm chooses i
1
, which is the element with the minimum finish 
time. Now, let r > 1 and assume that our hypothesis holds for r - 1. The question then becomes whether it is possible 
for the greedy algorithm to “fall behind” at this step. That is, is it possible that the finish time for i
r
 could now be 
greater than that of j
r
? The answer is clearly no, because the greedy algorithm could just as well have chosen j
r
 (which 
is compatible with j
r-1
, and therefore also with i
r-1
, which finishes at least as early).

---

Chapter 7 
■
 Greed Is Good? prove It! 
157
So, the greedy algorithm keeps up with the best, all the way to the end. However, this “keeping up” dealt only with 
finishing times, not the number of intervals. We need to show that keeping up will yield an optimal solution, and we 
can do so by contradiction: If the greedy algorithm is not optimal, then m > k. For every r, including r = k, we know 
that i
r
 finishes at least as early as j
r
. Because m > k, there must be an interval j
r+1
 that we didn’t use. This must start after 
j
r
, and therefore after i
r
, which means that we could have—and, indeed, would have—included it. In other words, we 
have a contradiction.
No Worse Than Perfect
This is a technique I used in showing the greedy choice property for Huffman’s algorithm. It involves showing that you 
can transform a hypothetical optimal solution to the greedy one, without reducing the quality. Kleinberg and Tardos 
call this an exchange argument. Let’s put a twist on the interval problem. Instead of having fixed starting and ending 
times, we now have a duration and a deadline, and you’re free to schedule the intervals—let’s call them tasks—as you 
want, as long as they don’t overlap. You also have a given starting time, of course.
However, any task that goes past its deadline incurs a penalty equal to its delay, and you want to minimize the 
maximum of these delays. On the surface, this might seem like a rather complex scheduling problem (and, indeed, 
many scheduling problems are really hard to solve). Surprisingly, though, you can find the optimum schedule through 
a super-simple greedy strategy: Always perform the most urgent task. As is often the case for greedy algorithms, the 
correctness proof is a bit tougher than the algorithm itself.
The greedy solution has no gaps in it. As soon as we’re done with one task, we start the next. There will also be 
at least one optimal solution without gaps—if we have an optimal solution with gaps, we can always close these up, 
resulting in earlier finish times for the later tasks. Also, the greedy solution will have no inversions (jobs scheduled 
before other jobs with earlier deadlines). We can show that all solutions without gaps or inversions have the same 
maximum delay. Two such solutions can differ only in the order of tasks with identical deadlines, and these must be 
scheduled consecutively. Among the tasks in such a consecutive block, the maximum delay depends only on the last 
task, and this delay doesn’t depend on the order of the tasks.
The only thing that remains to be proven is that there exists an optimal solution without gaps or inversions, 
because it would be equivalent to the greedy solution. This proof has three parts:
If the optimal solution has an inversion, there are two consecutive tasks where the first has a 
•
later deadline than the second.
Switching these two removes one inversion.
•
Removing this inversion will not increase the maximum delay.
•
The first point should be obvious enough. Between two inverted tasks, there must be some point where the 
deadlines start decreasing, giving us the two consecutive, inverted tasks. As for the second point, swapping the tasks 
clearly removes one inversion, and no new inversions are created. The third point requires a little care. Swapping tasks