Source code online books for professionals by professionals

i and j (so j now comes first) can potentially increase the lateness of only i; all other tasks are safe. In the new schedule, 
i finishes where j finished before. Because (by assumption) the deadline of i was later than that of j, the delay cannot 
possibly have increased. Thus, the third part of the proof is done.
It should be clear that these parts together show that the greedy schedule minimizes the maximum delay.
Staying Safe
This is where we started: To make sure a greedy algorithm is correct, we must make sure each greedy step along the 
way is safe. One way of doing this is the two-part approach of showing (1) the greedy choice property, that is, that a 
greedy choice is compatible with optimality, and (2) optimal substructure, that is, that the remaining subproblem is a 
smaller instance that must also be solved optimally. The greedy choice property, for example, can be shown using an 
exchange argument (as was done for the Huffman algorithm).

---

Chapter 7 
■
 Greed Is Good? prove It! 
158
Another possibility is to treat safety as an invariant. Or, in the words of Michael Soltys (see the “References” 
section of Chapter 4), we need to show that if we have a promising partial solution, a greedy choice will yield a new, 
bigger solution that is also promising. A partial solution is promising if it can be extended to an optimal solution. This 
is the approach I took in the section “What about the rest?” earlier in this chapter; there, a solution was promising 
if it was contained in (and, thus, could be extended to) a minimum spanning tree. Showing that “the current partial 
solution is promising” is an invariant of the greedy algorithm, as you keep making greedy choices, is really all you need.
Let’s consider a final problem involving time intervals. The problem is simple enough, and so is the algorithm, 
but the correctness proof is rather involved.
16
 It can serve as an example of the effort that may be required to show that 
a relatively simple greedy algorithm is correct.
This time, we once again have a set of tasks with deadlines, as well as a starting time (such as the present). This 
time, though, these are hard deadlines—if we can’t get a task done before its deadline, we can’t take it on at all. In 
addition, each task has a given profit associated with it. As before, we can perform only one task at a time, and we 
can’t split them into pieces, so we’re looking for a set of jobs that we can actually do, and that gives us as large a total 
profit as possible. However, to keep things simple, this time all tasks take the same amount of time—one time step.  
If d is the latest deadline, as measured in time steps from the starting point, we can start with an empty schedule of d 
empty slots and then fill those slots with tasks.
The solution to this problem is, in a way, doubly greedy. First, we consider the tasks by decreasing profit, starting 
with the most profitable task; that’s the first greedy part. Then comes the second part: We place each task in the latest 
possible free slot that it can occupy, based on its deadline. If there is no free, valid slot, we discard the task.  
Once we’re done, if we haven’t filled all the slots, we’re certainly free to perform tasks earlier, so as to remove the 
gaps—it won’t affect the profit or allow us to perform any more tasks. To get a feel for this solution, you might want to 
actually implement it (Exercise 7-20).
The solution sounds intuitively appealing; we give the profitable tasks precedence, and we make sure they use a 
minimum of our precious “early time,” by pushing them as far toward their deadline as possible. But, once again, we 
won’t rely on intuition. We’ll use a bit of induction, showing that as we add tasks in this greedy fashion, our schedule 
stays promising.
Caution
 
■
  the following presentation does not involve any deep math or rocket science and is more of an informal 
explanation than a full, technical proof. still, it is a bit involved and might hurt your brain. If you don’t feel up to it, feel free 
to skip ahead to the chapter summary.
As is invariably the case, the initial, empty solution is promising. In moving beyond the base case, it’s important 
to remember that the schedule is really promising only if it can be extended to an optimal schedule using the