MIT 6.1220 — Lecture 1

Greedy and DP

Problem. (Interval Scheduling) Consider a set of $n$ requests $R = \{(a_i, b_i)\}_{i = 1}^n$ , where:

Every request $r_i := (a_i, b_i)$ is an open interval with real number endpoints $a_i< b_i$ .
Two requests $r_i, r_j$ are compatible if they do not intersect.

Determine any largest possible subset of mutually compatible requests.

Example. If $R = \{(1, 2), (1, 3), (1, 4)\}$ , then any one of $\{(1, 2)\}$ , $\{(1, 3)\}$ , or $\{(1, 4)\}$ is an optimal solution.

Solution. (Interval Scheduling) Greedily pick the compatible requests that end earliest.

Proof: We define the following:

Let $S_{\textsc{GREEDY}} := \{s_i\}_{i = 1}^m$ be the ordered greedy solution (sorted by endpoint).
Let $S_{\textsc{OPT}} := \{s_i'\}_{i = 1}^{m'}$ be the ordered optimal solution (sorted by endpoint).

If $S_{\textsc{GREEDY}} = S_{\textsc{OPT}}$ , then we win. Otherwise, let $j^*$ be the first index where $S_{\textsc{GREEDY}}$ and $S_{\textsc{OPT}}$ differ.

Claim 1. If $j^* > 1$ , then $b_{j^* - 1} \leq a_{j^*}'$ . This is because $s_{j^* - 1} = s_{j^* - 1}'$ is assumed compatible with $s_{j^*}'$ .

Claim 2. We must have $b_{j^*} \leq b_{j^*}'$ . This is because the greedy algorithm picked $s_{j^*}$ , not $s_{j^*}'$ .

Claim 3. By Claim 1 and Claim 2, the optimal solution can be adjusted like so:
$\{s_1, \dots, s_{j^* - 1}, s_{j^*}', \dots, s_{m'}'\} \mapsto \{s_1, \dots, s_{j^*}, s_{j^* + 1}', \dots, s_{m'}'\}.$

By repeatedly applying Claim 3, we see $S = \{s_1, \dots, s_m, s_{m + 1}', \dots, s_{m'}'\}$ is an optimal solution. But $m' > m$ is impossible! If it were, the greedy algorithm would have added $(s_{m + 1}', \dots, s_{m'}')$ , yet it didn't. So $m = m'$ . $\blacksquare$

Problem. (Weighted Interval Scheduling) Consider a set of $n$ requests $R = \{(a_i, b_i)\}_{i = 1}^n$ together with weights $\{w_i\}_{i = 1}^n$ . Determine any heaviest possible subset of compatible weighted requests.

Solution. (Weighted Interval Scheduling) Just use DP. Sort the intervals by start time. Then:

W(R) = \max \{ W(\{r_2, \dots, r_n\}), \ \ w_1 + W(\{r_j \mid j \geq t_1\})\},

where $t_i$ is the least index $j > i$ for which $r_j$ does not intersect $r_i$ . Repeat, recurse, blah blah.

Remark. For any $i$ , how can you find $t_i$ in $O(\log n)$ time?

How can you find all the $t_i$ in $O(n)$ time, given the ordering of all interval endpoints?

Problem. (Online Interval Scheduling) Determine any largest possible subset of mutually compatible requests, given that requests come one at a time (in any order!) and must be accepted or rejected on arrival.

Unfortunately, an adversary can force the algorithm solver to always fail horribly. (Why?)

Problem. (Randomized Online Interval Scheduling) Say the set of requests $R$ is fixed. Now the algorithm receives these requests in a randomized order.

We'll figure out the solution to this updated problem during Probability Review on Sunday.