Chapter 4: Greedy Algorithms

A greedy algorithm creates a solution by making the optimal choice at a local level in the hopes of creating a solution that is globally optimal. The easiest example of this is giving change in the way that uses the least amount of coins. There are several ways to prove that the greedy solution is the optimal solution. The two this chapter discusses are greedy stays ahead and exchange (swappy). The motivation by the greedy algorithm is to solve a non-trivial problem optimally and can be used to solve interesting problems.

The Interval Scheduling problem is a problem where we have n intervals that each have a specific start and finish time. We want to perform as many of these n tasks as possible but the intervals cannot overlap , i.e. they are compatible. The section traces through several ways we could order the intervals prior to running the greedy algorithm, providing counter-examples to the orderings that are not optimal.The optimal ordering has been found to be ordering the intervals by the time they finish. Then we choose the job the finishes first thus allowing us to maximize the time we have left to perform other jobs. If we order the intervals in this way the algorithm (text page 118) will return an optimal ordering of intervals. In order to prove that the greedy solution is the optimal solution