4.1. Interval Scheduling: The Greedy Algorithm Stays Ahead

The Greedy Algorithm stays ahead means that if we measure the greedy algorithm's progress in a step-by-step fashion, we see that it does better than any other algorithm. Thus it produces an optimal solution. For the Interval Scheduling Problem, we have a set of requests {1,2,3,…,n} where the i^th request corresponds to an interval of time starting at S(i) and finishing at f(i). A subset of requests is compatible if no two of them overlap in time,and our goal is to accept as large a compatible subset as possible. Compatible subsets of maximum size are called optimal.