11 Interval Scheduling
This section discusses another set of problems where greedy algorithms can often be optimal.
Objectives. After learning this material, you should be able to:
- Define the interval scheduling problem and execute greedy algorithms for it.
- Prove that greedy is correct via an exchange argument.
- Decide for which variants greedy is not correct and provide counterexamples.
11.1 The interval scheduling problem
Interval scheduling is a problem where we have a resource available over time, and a set of requests to use the resource. An example would be a server and requests to use the server to run heavy computations; another would be a soccer field and requests to schedule games.
Each request will have a start and end time. Our goal is to schedule as many requests as possible, but we are not allowed to have overlapping requests.
Interval scheduling problem:
- Input: a list of requests \(i=1,\dots,n\). Each has a start time \(s(i)\) and an end time \(t(i)\), which we can assume are integers.
- Output: a subset \(S\) of the requests that we want to schedule. The subset must not be overlapping, i.e. only one request may be executing at any given time. The goal is to maximize the size of the subset.
As always when you see a new problem, it’s good to do some examples.
Exercise 11.1 Given the following instance of interval scheduling, what is the optimal solution? Are there more than one?
| \(i\) | \(s(i)\) | \(t(i)\) |
|---|---|---|
| 1 | 0 | 40 |
| 2 | 10 | 30 |
| 3 | 35 | 80 |
| 4 | 50 | 65 |
| 5 | 75 | 100 |
Hint: draw a diagram like this…
Solution.
The maximum number of requests we can schedule is three. There are two optimal solutions: \(\{1,4,5\}\) and \(\{2,4,5\}\). In either case, there are no overlaps and we schedule 3 different requests. There is no way to schedule four or five requests.
11.2 First greedy attempt
There are many possible greedy strategies here. Let’s brainstorm a few greedy algorithms. Can you think of any?
A few to get started.
- Always pick the smallest interval (that doesn’t overlap with any that you’ve picked so far).
- Always pick the an interval that overlaps with as few others as possible.
Can you think of other greedy strategies?
It turns out that a number of natural-looking greedy strategies don’t actually work. Let’s try disproving one.
Exercise 11.2 Using a counterexample, prove that the algorithm that always picks the smallest valid interval is not optimal.
Example solution.
There are many possible answers; here’s one.
The optimal solution is \(\{1,3\}\), giving us two intervals. But the greedy-by-smallest algorithm would first pick interval 2. Then it would not be able to pick any more intervals, so it would have a solution size of just one interval.
11.3 A correct greedy algorithm
It turns out this problem does have a greedy algorithm that optimally solves it, but we have to be a bit clever about what to be greedy with. Here’s the algorithm:
- Select the interval that is scheduled to finish first, i.e. has minimum \(t(i)\). Remove from consideration any intervals that overlap with it.
- Repeat until no intervals remain.
Theorem 11.1 The above algorithm, greedy by first finish time, is correct for interval scheduling.
Proof. We will use an exchange argument. Suppose greedy selects the requests \(S = \{ i_1,\dots,i_k \}\), in order of start time and finish time. Consider any other feasible solution (meaning no overlaps), \(R = \{j_1,\dots,j_r\}\), also in order of start and finish time. We want to show that \(k \geq r\), that is, greedy selects at least as many requests.
First, because of how greedy works, \(t(i_1) \leq t(j_1)\). So we can remove \(j_1\) from \(R\) and add \(i_1\) and \(R\) is still feasible, and the number of requests has not changed. Next, consider \(j_2\). We have \(s(j_2) > t(j_1) \geq t(i_1)\). So greedy could have added \(j_2\) next. But greedy added \(i_2\). Therefore, because of how greedy works, \(t(i_2) \leq t(j_2)\). So we can remove \(j_2\) from \(R\) and add \(i_2\) and \(R\) is still feasible, and the number of requests has not changed.
We repeat this argument until the very end. Suppose for contradiction that \(k < r\), so after we exchange \(i_k\) into \(R\) for \(j_k\), there still remains some request \(j_{k+1}\). If this were possible, then greedy would have added \(j_{k+1}\) to its solution, since it is feasible (we must have \(s(j_{k+1}) > t(j_k) \geq t(i_k)\)). This is a contradiction. We conclude \(k \geq r\).