This is an old revision of the document!
Chapter 4
Section 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead
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:
