Chapter 4.1: Interval Scheduling

We have a set of requests {1,2,…,n} where the ith request corresponds to an interval of time starting at s(i) and finishing at f(i). A subset of the requests is compatible if no two of them overlap in time, and the goal is to choose the largest possible subset of requests. Compatible sets of maximum size are optimal.

Greedy Stays Ahead The basic idea behind a greedy algorithm is to use a rule to select the first request, i_1. Once the first request is accepted, we reject all requests that are not compatible with i_1. Then we select the next request to be accepted, and again reject all requests that are not compatible with i_2. We continue in this way until we run out of requests. The challenge in designing this algorithm is choosing what rule to use. Some possibilities:

• Select requests based on earliest starting time
• Select requests based on smallest interval of time (minimizing f(i)-s(i))
• Select requests based on lowest number of conflicts with other requests
• Select requests based on earliest finishing time

The first three rules do not produce an optimal solution (check lecture notes for diagrams of counterexamples). The fourth rule, sorting by earliest finishing time, is what we should use.

Let's say that there is the greedy solution and the optimal solution. By induction, we can prove that the greedy solution is optimal. The greedy stays ahead algorithm chooses the optimal solution every step of the way, choosing requests that end either before or at the same time as the optimal solution's choices. So if at the k+1 step, the optimal solution's choice ends before greedy's, we have a contradiction because greedy would have chosen the request that ended earlier. So the greedy solution is optimal.

This algorithm runs in O(nlogn) time. We must first sort the n requests in order of earliest finish time (logn). Then we pass through each of the n requests (n) so our overall running time is nlogn.

This problem could be extended if each request had a certain value assigned to it. So our goal is to not only schedule a maximum number of requests, but also maximize the value as well. We could also extend this to a “scheduling all intervals” problem. In other words, this can become an interval partitioning problem where we try and schedule all results while at the same time using as few resources as possible. In this instance, the number of resources needed is at least the depth of the set of intervals. For a set, the largest number of conflicts is the depth of the set.

We can sort the intervals by start time (breaking ties arbitrarily). Then we choose the first interval to go into the first resource. Then we choose the second interval. If it doesn't conflict with the previous interval, add it to that resource. If it does conflict, create a new resource and add it there. Then we choose the next interval, check it against the first resource and (if necessary), the second resource. Continuing in this way, every interval will be assigned a resource and not two over-lapping intervals will be in the same resource. The greedy algorithm in this case yields the optimal number of resources needed.

I'd rate this section a 9. I understood it, but I think it's only because our lecture came first. The diagrams from the slides helped me to visualize what was going on in this chapter.