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.

–> The basic idea when designing a greedy algorithm for the interval scheduling problem is to select a first request i₁. Once the first request is selected, all of the requests not compatible with it are rejected. We then select the next request i₂ to be accepted,and eliminate all of the requests not compatible with it. We continue in this way until there are no more requests.

–>Thus the biggest issue is to find a simple way of selecting requests.

–> After examining the number of options we can use to select the first request, it turns out that the best choice is to select a request with the fewest conflicts possible: the request with the fewest number of non compatible requests.