A greedy algorithm uses small steps to formulate its solution. In each step, a decision is made to optimize the solution at that step. A greedy algorithm tells use that there is some rule we can use to make small decisions that will ultimately lead us to an optimal solution. Sometimes, greedy algorithms produce solutions that are close to optimal, but not quite optimal. A greedy algorithm works by staying ahead of the optimal solution at each step. There is also the “exchange argument” that says a possible solution can be turned into the greedy algorithm solution without altering its optimality.

The interval scheduling problems consists of a set of intervals (start and stop times) that must be scheduled for a single resource. The optimal solution is the largest set of intervals such that there is no overlap. While there are a few intuitive ways to think about how we might want to solve this problem, the greedy algorithm is based on end time. We always schedule the interval that finishes first in our set, unless that interval conflicts with the previous intervals already to our solution. To prove the solution is optimal, we must show that the greedy algorithm “stays ahead” of any other optimal solution. Each i^th accepted request will finish at least as soon as the i^th accepted request in an optimal solution, which means the greedy algorithm stays ahead of any other optimal solution. The efficiency of the algorithm to calculate this set of intervals is O(nlogn).

The problem in this scenario is that of a single resource that must be scheduled with jobs that take a certain amount of time and have a deadline, but no set start time. The objective is to schedule all jobs in a way that minimized the maximum lateness incurred by any one job.