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.

–> To select the first request, we examine a number of options,and decide which greedy rule can give us the optimal solution. It turns out that one of the best choices would be to select a request with the fewest conflicts possible: the request with the fewest number of non compatible requests. When we can find a counterexample to our best choice greedy rule, we can still use another greedy rule to find an optimal solution. In this case, we choose the greedy rule that gives us the next big subset with the fewest number of non compatible requests

Let R be a set of all requests, and let A be the set of accepted requests
Initially, let A be empty
While R is not empty

Choose a request i in R that has the smallest finishing time
Add request i to A
Delete all requests from R that are not compatible with request i

End While
Return the set A as the set of accepted requests

• The set A returned is that of compatible requests and it is optimal.
• For all indices r ≤ k, we have f(i_r) ≤ f(j_r), f(j_r) being the finishing time of the request in the optimal solution corresponding to the request f(i_r) in A

–>Our goal: A O(nlogn)running time

First sort the n requests in order of finishing time and label them in this order:f(i) ≤ f(j) if i ≤ j. Sorting takes O(nlogn) time)
We then construct an array S[1,…,n] where S[i] contains the value S(i). This takes O(n) time.

Now we select requests in order of increasing f(i). We always select the first interval.
Then iterate through the interval in order until S(j) ≥ f(1). We then select this interval S(j).
In this way, we spend O(1) time per each interval and implement our greedy rule in a single pass through the intervals. This part of the algorithm takes O(n) time.