An greedy algorithm is accurate to its name. It builds up a solution greedily, by choosing a decision at each step that optimizes the solution at that point. While greedy algorithms can be designed for many problems, the ones we want to concern ourselves with are the ones that have optimal greedy solutions. Thus, most of this chapter will be concerned with constructing a greedy algorithm and then proving it is optimal, using either the greedy stays ahead argument or the exchange argument.

The Interval Scheduling Problem was introduced in chapter 1.2 and basically consists of try to schedule the largest subset of requests(with start and end times) possible without overlap. The easiest concrete example is trying to schedule meetings in a single meeting room. The key to designing an optimal greedy algorithm to solve this problem is to determine what rule to use to choose the requests. Several options, including choosing by earliest start time or smallest interval of time, provide solutions, but they are not optimal. Instead, we want to order the requests by finish time. From there, you simply pick the first one, then go down the list choosing the first one that does not overlap, and so on. The algorithm is on page 118.

To analyze the algorithm we show that our algorithm “stays ahead” of the optimal solution at every point. We can prove that for every r, the r accepted request in our algorithm finishes no later than the r request in the optimal solution. By ordering the requests by finish time, out algorithm will run in O(nlogn) time. There are also several extensions of this project such as scheduling weighted requests or scheduling requests without knowing all of them ahead of time.

A similar problem is scheduling all intervals, with the goals of using the fewest possible resources. We prove in this section that the number of resources needed is equal to the depth of the set of intervals. The depth is the maximum number of requests that overlap. It is impossible to have a solution with less resources than the depth and you cannot have an optimal solution with more resources than the depth. The algorithm on page 124 orders requests by their start time and is optimal.