Summary
Described and analyzed a greedy solution to Interval Scheduling. Then, introduced a weighted variant which required a dynamic programming solution, and introduced online interval scheduling as an additional interesting problem.
Introduction
We will be covering design and analysis of algorithms. For design, we will look through techniques (greedy, divide-and-conquer, LP, etc.), paradigms (randomized, online, sublinear, sketching, sampling, etc.), and more. For analysis, we’ll look at amortized, competitive, approximation, and much more. Additionally, we will talk about designability of algorithms, namely intractability and reductions.
Interval Scheduling
The idea is that we have requests , each wanting a single resource for an interval and are real. Find a largest set of mutually compatible requests.
- Two requests are mutually compatible if they don’t intersect; else, incompatible
- A set of >2 requests is mutually compatible iff each pair is
Example
. Choosing any one is the optimal solution.
We can draw out these intervals on a number line, though it becomes harder to parse as the intervals become more numerous.
We will design a greedy meta-algorithm (main idea, but not complete) to solve this problem.
- Set
- Repeat until :
- Use the greedy rule to pick . ← sort
- If compatible with , ←
- Set
- Output Our choice of the greedy rule determines the correctness of the algorithm. Choosing earliest start time is bad, as you can have a situation where the earliest interval takes up the whole interval, for instance.
Shortest interval first also is incorrect: you might have a short interval intersecting two otherwise compatible long intervals.
The correct greedy choice is earliest end time. We will use the exchange argument to prove the greedy choice:
Proof (Exchange Argument)
Let and ordered by end time. Want .
Claim: for all (greedy ends no later than OPT at each step).
Proof: Induction. Since , anything compatible with OPT is compatible with greedy, so greedy has at least as many choices and picks earliest.
Conclusion: If , then is compatible with (since ), so greedy would have selected it—contradiction.
The final runtime is .
Weighted Interval Scheduling Problem
This is the same problem as before, but each request has a weight . We want to find the heaviest set of mutually compatible requests.
Notice that our current greedy choice no longer works. The reason is left as an exercise. Instead, we need to use the optimal substructure property and build a dynamic program.
Let us restrict to finding the weight of the optimal solution. Given , let denote the maximum possible total weight for a set of mutually compatible requests in . For any of weight , let denote the subset of requests from that are incompatible.
This expression essentially says that, in the first case, if the optimal solution doesn’t have , we can exclude it from . If it is a part of the optimal solution, we add its weight along with the remainder of excluding incompatible elements with . For size , we have:
Claim
for some index .
Why? Since requests are sorted by end time, ends last. Any request overlapping must start before ends. These form a contiguous suffix : all requests from index onward overlap with .
The left is with excluded, and the second with it included. is the first interval incompatible with , so we keep the prefix when including .
We can continue unwinding. For the DP solution:
- Sort by end time. ←
- Find for ← through binary search
- For compute
← linear sweep 4) Output So total runtime is .
Online Interval Scheduling Problem
Here, we don’t have all the intervals upfront. They will come in one at a time. We can think of it as an adversary who wants to make the problem harder. We can either change the problem or setting: today, we’ll change the setting.
Say the set of intervals is fixed. Someone shuffles the intervals in a random way. With what chance are things going to go badly with some greedy choice? We need probabilistic methods to solve this.
In this case, if we randomly get first, it’s optimal.