Chapter 4

The motivation for interval scheduling is to schedule as many jobs as possible with no overlap between the intervals of time for each job. When designing a greedy algorithm for this problem, we base the algorithm on one simple rule; e.g. selecting jobs that start the earliest, or jobs with smallest interval times. In this problem, the simple rule that produces an optimal solution is selecting jobs that finish the earliest. The greedy algorithm looks like such:

   R = set of all jobs, A is an empty set
   while R != empty
        choose a job R(i) that has smallest finishing time
        add i to A
        delete all jobs from R that are not compatible with i
   return A
   

In this algorithm, we simply add the job i that ends as soon as possible, then remove all jobs that conflict with i. We then repeat this until there are no more jobs, resulting in a run time of O(n). We prove this algorithm returns a globally optimal solution using a Greedy Stays Ahead proof. Essentially, using a proof by contradiction, we declare an optimal set O that contains the most optimal scheduling of jobs compared to greedy's set A. If this were the case, O must have more jobs scheduled than A; however, if there was an additional optimal job, it would be in A, a contradiction. Thus, A must be as optimal as O.