Chapter 4

A greedy algorithm is one that builds up a solution in small steps to optimize something. We will use greedy algorithms for many problems including the shortest path problem, the Minimum Spanning Tree problem and others. There are two main proof techniques for showing a greedy algorithm works: the greedy stays ahead proof and the exchange argument.

We can use the greedy algorithm to solve the interval scheduling problem. Given n intervals (with start and end times), we want to find the largest compatible (non-overlapping) set of these intervals. We can do this by successively choosing the interval with the earliest end time that does not conflict with our current set of accepted intervals. We can prove this works with a “greedy stays ahead” inductive proof. The algorithm has O(nlogn) run time. (p 118)

A related problem is that of scheduling all intervals in the fewest number of rooms (Interval Partitioning Problem). In this problem with optimal number of rooms is the depth of the intervals. We can achieve an optimal schedule with a greedy algorithm that orders the intervals by start time and assigns them to the first room in which there are no conflicts. (p 124)

Readability: 7

We can also use greedy to solve the Minimum Lateness Problem. In this problem, we have tasks with deadlines and we want to schedule them so maximum lateness is minimized. By processing the tasks in order of earliest deadlines, we can accomplish this. To prove this works, we use an exchange argument. First we note that there is an optimal schedule with no idle time and that two schedules with no idle time and no inversions (a situation where a job with an earlier deadline is scheduled after a job with a later deadline) have the same max lateness. Then we show that by swapping inversions in some optimal schedule, we maintain its optimality and end up with the same max lateness as our schedule.

Readability: 7