--- title: Scheduling & Interval Partitioning module: Greedy Algorithms moduleNumber: 7 lessonNumber: 2 order: 702 summary: | Three classic scheduling problems all yield to greedy algorithms — and all three turn on a single design decision: which key to sort by. Interval scheduling sorts by **finish** time to pack the most compatible jobs; interval partitioning sorts by **start** time and proves the rooms needed equal the maximum overlap **depth**; minimizing maximum lateness sorts by **deadline** and is justified by an adjacent-swap exchange argument. topics: [Greedy] sources: - book: CLRS ref: "Ch. 16 — Greedy Algorithms (§16.1)" - book: Skiena ref: "§ — Scheduling" - book: Erickson ref: "Ch. — Greedy Algorithms" practice: - title: 'Non-overlapping Intervals' slug: non-overlapping-intervals difficulty: Medium - title: 'Minimum Number of Arrows to Burst Balloons' slug: minimum-number-of-arrows-to-burst-balloons difficulty: Medium - title: 'Meeting Rooms II' slug: meeting-rooms-ii difficulty: Medium - title: 'Car Pooling' slug: car-pooling difficulty: Medium - title: 'Task Scheduler' slug: task-scheduler difficulty: Medium --- The previous lesson introduced the greedy method on its canonical example: **activity selection**, where we pick a maximum-size set of mutually compatible intervals by repeatedly taking the one that finishes earliest. That was a single problem solved by a single sort key. This lesson covers the whole family of **interval and scheduling problems** that the [greedy method](/algorithms/greedy/the-greedy-method) solves; they are nearly the same algorithm with different sort keys. Sort by **finish** time to maximize how many jobs fit; by **start** time to minimize how many machines you need; by **deadline** to minimize how late the worst job runs. Choosing the key correctly, and proving that choice optimal, is the entire problem. ## Interval scheduling, recapped Recall the setup. We are given $n$ intervals, interval $i$ being the half-open $[s_i, f_i)$, and two intervals are **compatible** when they do not overlap. We want a maximum-size set of pairwise compatible intervals, the most jobs we can run on one machine without conflict.[^clrs-activity] The greedy rule, proved correct last lesson, is **earliest finish time first**: sort by $f_i$, take the first interval, discard everything that overlaps it, and recurse on the rest. The selection itself is one linear scan, so after the [sort](/algorithms/sorting/heaps-and-heapsort) the algorithm runs in $\O(n\log n)$. > **Remark (Why it is optimal).** The argument is a _stays-ahead_ / exchange > argument. Let $a_1$ be the earliest-finishing interval. Some optimal solution > $S^\star$ can be edited to contain $a_1$: if its first interval $j$ differs from > $a_1$, swap $a_1$ in for $j$. Since $f_{a_1} \le f_j$, every later interval of > $S^\star$, which started after $f_j$, still starts after $f_{a_1}$, so the > swapped set is valid and no smaller. The greedy choice is therefore safe; > induction on the remaining intervals (all of which start at or after $f_{a_1}$) > finishes the proof. Greedy never falls behind: pick the earliest-finishing interval each round, and greedy's $k$-th choice frees the machine no later than any rival schedule's $k$-th, so it always has at least as much room left. $$ % caption: Earliest-finish-first stays ahead. Greedy's $k$-th interval (green) finishes no % later than the $k$-th interval of any other compatible schedule (gray), so % greedy always has at least as much room left. \begin{tikzpicture}[xscale=0.62, yscale=0.62, g/.style={draw=acc, very thick, minimum height=4.5mm, fill=acc!15}, o/.style={draw, thick, minimum height=4.5mm, fill=black!10}] \definecolor{acc}{HTML}{2348F2} \node[font=\footnotesize, align=right] at (-1.6,3.4) {greedy}; \node[g, minimum width=1.8cm] at (0.9,3.4) {$g_1$}; \node[g, minimum width=1.8cm] at (3.3,3.4) {$g_2$}; \node[g, minimum width=1.8cm] at (5.7,3.4) {$g_3$}; \node[font=\footnotesize, align=right] at (-1.6,1.8) {other}; \node[o, minimum width=2.6cm] at (1.3,1.8) {$o_1$}; \node[o, minimum width=2.2cm] at (4.0,1.8) {$o_2$}; \node[o, minimum width=1.8cm] at (6.3,1.8) {$o_3$}; \draw[acc, dashed] (1.8,3.7) -- (1.8,0.9); \draw[acc, dashed] (2.6,2.1) -- (2.6,0.9); \node[acc, font=\footnotesize] at (2.2,0.4) {$f_{g_1}$ not after $f_{o_1}$}; \draw[->, thick] (-1.0,-0.1) -- (7.4,-0.1) node[right, font=\footnotesize] {time}; \end{tikzpicture} $$ For example, take five requests for one machine, already sorted by finish time: | Interval | $a\,[1,4)$ | $b\,[3,5)$ | $c\,[0,6)$ | $d\,[5,7)$ | $e\,[6,8)$ | | --- | --- | --- | --- | --- | --- | | finish $f_i$ | 4 | 5 | 6 | 7 | 8 | Scanning in finish order and keeping $f_{\text{last}}$, the finish of the most recently accepted interval: | Step | Interval | $[s,f)$ | $f_{\text{last}}$ before | $s \ge f_{\text{last}}$? | Action | | --- | --- | --- | --- | --- | --- | | 1 | $a$ | $[1,4)$ | — | — | accept, $f_{\text{last}}\gets 4$ | | 2 | $b$ | $[3,5)$ | $4$ | $3 \ge 4$? no | reject | | 3 | $c$ | $[0,6)$ | $4$ | $0 \ge 4$? no | reject | | 4 | $d$ | $[5,7)$ | $4$ | $5 \ge 4$? yes | accept, $f_{\text{last}}\gets 7$ | | 5 | $e$ | $[6,8)$ | $7$ | $6 \ge 7$? no | reject | Greedy accepts $\{a, d\}$, a maximum set of two: no three of these five intervals are pairwise compatible, since $c$ alone overlaps every other, and $a, b, c$ share the point $t=3.5$. The rule discards $b$ and $c$ the moment they overlap the last acceptance, and never revisits them. The output is a maximum-size set of mutually compatible intervals, computed in $\O(n\log n)$. Everything below reuses this skeleton (sort, scan, exchange-argument proof) with a different key and a different objective. ::impl{algo="interval_scheduling"} ## Interval partitioning: minimize the rooms Now flip the question. Instead of dropping intervals to fit on one machine, we keep _all_ of them and ask for the fewest **machines** (rooms, colors, frequencies) needed to run them, where two intervals sharing a machine must be compatible. Phrased as graph coloring: color the intervals so that any two overlapping intervals get different colors, using the minimum number of colors.[^skiena-sched] The right invariant is **depth**. Define the depth at a point $t$ as the number of intervals containing $t$, and let $d = \max_t \text{depth}(t)$ be the maximum over all points. Depth is a hard lower bound on rooms, and greedy matches it. $$ % caption: colors needed = max overlap depth $d$ (highlighted line crosses 3 intervals) \begin{tikzpicture}[ font=\small, >=stealth, bar/.style={line width=3pt}] \definecolor{acc}{HTML}{2348F2} % timeline axis \draw[->] (0,-0.4) -- (9.2,-0.4) node[right]{time}; % room 1 (y=2.4) \draw[bar] (0.3,2.4) -- (2.6,2.4); \draw[bar] (3.2,2.4) -- (5.4,2.4); \draw[bar] (6.0,2.4) -- (8.6,2.4); \node[left] at (0.3,2.4) {R1}; % room 2 (y=1.4) \draw[bar] (1.4,1.4) -- (4.2,1.4); \draw[bar] (4.8,1.4) -- (8.0,1.4); \node[left] at (1.4,1.4) {R2}; % room 3 (y=0.4) \draw[bar] (3.6,0.4) -- (6.6,0.4); \node[left] at (3.6,0.4) {R3}; % max-depth line: t where R1(3.2-5.4), R2(1.4-4.2), R3(3.6-6.6) all overlap \draw[acc, line width=1pt, dashed] (3.9,-0.4) -- (3.9,2.9); \node[acc, above] at (3.9,2.9) {$d=3$}; \end{tikzpicture} $$ > **Lemma (Lower bound).** Any valid partition uses at least $d$ machines. _Proof._ At the > point $t$ of maximum depth there are $d$ intervals all containing $t$; they > pairwise overlap, so no two may share a machine, forcing at least $d$ distinct > machines. $\qed$ The greedy algorithm sorts by **start** time and keeps a [min-heap](/algorithms/sorting/heaps-and-heapsort) of machines keyed by the time each becomes free. For each interval in start order, if the machine that frees earliest is already free by this interval's start, reuse it; otherwise open a new machine. ```algorithm caption: $\textsc{Partition}(I)$ — fewest machines for intervals $I$ sort $I$ by start time $s_i$ ascending $H \gets$ empty min-heap of machines keyed by free time for each interval $i$ in start order do if $H$ nonempty and $\min(H).free \le s_i$ then $m \gets \textsc{Extract-Min}(H)$ // reuse earliest-freed machine else $m \gets$ new machine // none free: open one $m.free \gets f_i$ $\textsc{Insert}(H, m)$ return $|H|$ // total machines opened ``` We trace the scan. Intervals enter in **start** order; each reuses the machine that frees earliest if it is already free, otherwise it opens a new one. The third interval arrives while both open machines are still busy, so it forces a third; that instant is a point of depth $3$, the witness for the lower bound. $$ % caption: $\textsc{Partition}$ assigning six intervals in start order to three machines. % Interval $3$ (red) arrives while R1 and R2 are still busy, opening R3; later % intervals reuse a machine that has freed. The forced opening at $3$ is exactly % a depth-$3$ point. \begin{tikzpicture}[xscale=0.72, yscale=0.62, reuse/.style={draw=acc, very thick, minimum height=4.5mm, fill=acc!15}, open/.style={draw=red!75!black, very thick, minimum height=4.5mm, fill=red!18}] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-1.6,-1.0) rectangle (11.0,4.3); % room labels \node[font=\footnotesize] at (-1.1,2.6) {R1}; \node[font=\footnotesize] at (-1.1,1.6) {R2}; \node[font=\footnotesize] at (-1.1,0.6) {R3}; % R1: interval 1 [0,3), then 4 [4,7) \node[reuse, minimum width=3cm] at (1.5,2.6) {$1$}; \node[reuse, minimum width=3cm] at (5.5,2.6) {$4$}; % R2: interval 2 [1,4), then 5 [5,8) \node[reuse, minimum width=3cm] at (2.5,1.6) {$2$}; \node[reuse, minimum width=3cm] at (6.5,1.6) {$5$}; % R3: interval 3 [2,5) opens it, then 6 [6,9) \node[open, minimum width=3cm] at (3.5,0.6) {$3$}; \node[reuse, minimum width=3cm] at (7.5,0.6) {$6$}; % time axis \draw[->, thick] (0,-0.2) -- (9.6,-0.2) node[right, font=\footnotesize] {time}; \foreach \x in {0,1,...,9} \draw (\x,-0.1) -- (\x,-0.3) node[below=1pt, font=\tiny] {\x}; % depth-3 witness line at t=2.85 (inside intervals 1,2,3; clear of their labels) \draw[red!75!black, dashed] (2.85,0.1) -- (2.85,3.1); \node[red!75!black, font=\footnotesize, align=center] at (2.85,3.4) {opens R3:\\depth $3$}; \end{tikzpicture} $$ The min-heap is what makes each step cheap: it holds one entry per open machine, keyed by the time that machine next frees, so the earliest-freeing machine is always at the root. Walking the six intervals through it shows the heap state at each step. Each row lists the arriving interval, the root's free time, whether that machine can be reused, and the heap after the step. | Interval | $s_i$ | root free time | reuse? | machines | heap after (free times) | | --- | --- | --- | --- | --- | --- | | $1\,[0,3)$ | $0$ | — (empty) | open R1 | 1 | $\{3\}$ | | $2\,[1,4)$ | $1$ | $3$ | $3 \le 1$? no, open R2 | 2 | $\{3, 4\}$ | | $3\,[2,5)$ | $2$ | $3$ | $3 \le 2$? no, open R3 | 3 | $\{3, 4, 5\}$ | | $4\,[4,7)$ | $4$ | $3$ | $3 \le 4$? yes, reuse R1 | 3 | $\{4, 5, 7\}$ | | $5\,[5,8)$ | $5$ | $4$ | $4 \le 5$? yes, reuse R2 | 3 | $\{5, 7, 8\}$ | | $6\,[6,9)$ | $6$ | $5$ | $5 \le 6$? yes, reuse R3 | 3 | $\{7, 8, 9\}$ | The machine count climbs to $3$ over the first three intervals — precisely the depth-$3$ overlap of $1$, $2$, $3$ — and every later interval finds a freed machine at the root, so the count never rises again. The answer is $3$, matching $d$. > **Lemma (Greedy matches the bound).** $\textsc{Partition}$ never opens more than $d$ > machines. _Proof._ Suppose it opens a brand-new machine while processing > interval $i$. It does so only because _every_ machine already open is busy at > time $s_i$, each holding an interval $j$ with $s_j \le s_i < f_j$. Those > intervals, together with $i$, all contain the point $s_i$, so the depth at > $s_i$ is at least the number of machines open after this step. Hence whenever > the count of machines rises to $k$, some point has depth $\ge k$, so the final > count never exceeds $d$. Combined with the lower bound, greedy uses _exactly_ > $d$. $\qed$ Because we processed intervals in start order, no interval we open a machine for overlaps a _future_ interval that already passed, so the depth witness is real, not an artifact of order. The sort is $\O(n\log n)$ and each interval does $\O(\log n)$ heap work, for $\O(n\log n)$ overall.[^erickson-greedy] This is exactly LeetCode's _Meeting Rooms II_ and _Minimum Number of Arrows_ in disguise: the first asks for $d$ directly; the second asks for the complementary count of points that stab all intervals. ::impl{algo="interval_partitioning"} ## Minimizing maximum lateness The third problem changes the objective from _count_ to _timing_. We have one machine and $n$ jobs; job $j$ needs $t_j$ units of processing and has a **deadline** $d_j$. We must order the jobs (the machine runs one at a time, no preemption); if job $j$ finishes at time $f_j$ its **lateness** is $\ell_j = \max(0, f_j - d_j)$, and we want to minimize the **maximum lateness** $L = \max_j (f_j - d_j)$ across all jobs.[^clrs-activity] The greedy rule is **earliest deadline first** (EDF): ignore the processing times entirely, sort the jobs by deadline $d_j$, and run them back-to-back in that order with no idle gaps. The proof uses both qualifiers: no idle time and deadline order. ```algorithm caption: $\textsc{Min-Max-Lateness}(t, d)$ — order $n$ jobs to minimize worst lateness sort jobs so that $d_1 \le d_2 \le \cdots \le d_n$ // earliest deadline first $f \gets 0$ // running finish time, no idle gaps $L \gets 0$ // worst lateness so far for $j \gets 1$ to $n$ do $f \gets f + t_j$ // job $j$ finishes here $L \gets \max(L,\ f - d_j)$ // update max lateness return order $1,\dots,n$ with lateness $L$ ``` > **Lemma (exchange / no inversions).** Some optimal schedule has no idle time and > no **inversions**, where an inversion is a pair of jobs scheduled with the later > deadline first ($d_i > d_j$ but $i$ runs before $j$). The earliest-deadline-first > schedule is one such schedule, so it is optimal. > > **Proof.** Idle time only delays jobs, so removing it cannot increase any $f_j$, > hence cannot increase $L$; assume there is none. Now suppose an optimal schedule > has an inversion. Then it has an **adjacent** inversion: a pair $i, j$ run > consecutively with $i$ immediately before $j$ yet $d_i > d_j$. Swap them. Only > $i$ and $j$ move, and they occupy the same combined time slot, so every _other_ > job's finish time is unchanged. After the swap $j$ finishes earlier than $i$ did > before, so $j$'s lateness only drops. The new lateness of $i$ is its new finish > time — which equals the _old_ finish time of $j$ (the slot's right end) — minus > $d_i$; since $d_i > d_j$, this is at most the old lateness of $j$. So the > maximum of the two latenesses does not increase, and neither does $L$. > > Each adjacent swap removes one inversion without raising $L$. Repeating drives > the schedule to zero inversions, i.e. earliest-deadline-first order, proving > it optimal. $\qed$ $$ % caption: an adjacent EDF swap: exchanging an inversion ($d_i>d_j$) never raises max % lateness \begin{tikzpicture}[ font=\small, job/.style={draw, minimum height=7mm, inner sep=3pt}] \definecolor{acc}{HTML}{2348F2} % top: inverted order i then j, with d_i > d_j \node[left] at (-0.2,2) {inverted:}; \node[job, minimum width=22mm] (i1) at (1.5,2) {$i\ (d_i=9)$}; \node[job, minimum width=14mm, acc, draw=acc] (j1) at (3.7,2) {$j\ (d_j=5)$}; \node[acc, font=\footnotesize] at (5.4,2) {$j$ late}; % bottom: swapped, earliest deadline first \node[left] at (-0.2,0.4) {EDF:}; \node[job, minimum width=14mm, acc, draw=acc] (j2) at (1.1,0.4) {$j\ (d_j=5)$}; \node[job, minimum width=22mm] (i2) at (3.3,0.4) {$i\ (d_i=9)$}; % swap arrow (process arrow -> red) \draw[->, red!75!black, very thick] (2.6,1.55) -- (2.6,0.85) node[midway, left, font=\footnotesize]{swap}; \end{tikzpicture} $$ So minimizing maximum lateness is, again, sort-and-scan: sort by deadline in $\O(n\log n)$, run in that order, done. In a worked run, with the jobs in deadline order, each finish time falls out of the running total, and the lateness of the worst job is what we report. $$ % caption: Earliest-deadline-first on one machine. Jobs $A,B,C$ run back-to-back in % deadline order ($d_A{=}4,d_B{=}6,d_C{=}8$); each lateness is $\max(0,f_j-d_j)$, % and the schedule minimizes the worst, here $L=1$. \begin{tikzpicture}[xscale=0.85, yscale=0.6, font=\small] \definecolor{acc}{HTML}{2348F2} \node[draw, very thick, minimum height=6mm, minimum width=1.53cm, fill=black!8] at (0.9,2) {$A$}; \node[draw, very thick, minimum height=6mm, minimum width=2.04cm, fill=acc!18] at (3.0,2) {$B$}; \node[draw, very thick, minimum height=6mm, minimum width=1.02cm, fill=black!8] at (4.8,2) {$C$}; \draw[->, thick] (0,1.3) -- (6.0,1.3) node[right,font=\footnotesize]{time}; \foreach \x/\l in {0/0,1.8/3,4.2/7,5.4/9} \draw (\x,1.4)--(\x,1.2) node[below,font=\footnotesize]{\l}; \node[font=\footnotesize] at (0.7,2.85) {$f{=}3$, lat $0$}; \node[acc, font=\footnotesize] at (3.0,3.55) {$f{=}7$, lat $1$}; \node[font=\footnotesize] at (5.05,2.85) {$f{=}9$, lat $1$}; \node[red, font=\footnotesize] at (3.0,0.4) {worst lateness $L=1$}; \end{tikzpicture} $$ Here jobs $A$ (length $3$, deadline $4$), $B$ (length $4$, deadline $6$), and $C$ (length $2$, deadline $8$) run in deadline order $A, B, C$. Finish times are the running sums $3$, $7$, $9$; latenesses are $\max(0, 3-4)=0$, $\max(0, 7-6)=1$, $\max(0, 9-8)=1$, so $L = 1$. To see that no order does better, try the intuitive _shortest-job-first_ order $C, A, B$: now $C$ finishes at $2$ (lateness $0$), $A$ at $5$ (lateness $\max(0,5-4)=1$), and $B$ at $9$ (lateness $\max(0,9-6)=3$), giving $L = 3$ — three times worse. Sorting by length optimized the wrong thing; only the deadline order controls the _worst_ lateness, exactly what the adjacent-swap argument guarantees. ::impl{algo="minimum_lateness"} ## The trio, and the one decision These three — interval **scheduling**, interval **partitioning**, and maximum **lateness** — are the canonical greedy-on-intervals trio. They share a single shape: sort the intervals or jobs by one key, then make one pass. Everything distinctive about each lives in the key: | Problem | Objective | Sort key | Optimality proof | |---|---|---|---| | Scheduling | max compatible jobs | **finish** time | stays-ahead / exchange | | Partitioning | min machines | **start** time | depth lower bound = greedy | | Max lateness | min worst lateness | **deadline** | adjacent-swap exchange | The lesson is that for greedy interval problems the design work is almost entirely _choosing the sort key_, and the verification work is a short exchange or stays-ahead argument confirming the choice. Get the key right and the rest is a linear scan. ## Weights, online arrivals, and where greedy stops The three interval problems above all yield to a single sort. Two natural generalizations break the greedy rule, and the boundary is instructive. **Weighted interval scheduling.** Give each interval a _weight_ $w_i$ and ask for the maximum-weight compatible subset, not the maximum-count one. Earliest-finish greedy now fails: a single high-weight interval can be worth more than many cheap ones that would displace it. To address this, use **dynamic programming**. Sort by finish time, precompute for each interval $i$ the largest index $p(i)$ of an interval that ends at or before $i$ starts, and set $\mathrm{OPT}(i) = \max\{\,w_i + \mathrm{OPT}(p(i)),\ \mathrm{OPT}(i-1)\,\}$ — take $i$ (and jump to the last compatible predecessor) or skip it. The recurrence runs in $O(n\log n)$ and is the canonical example that the _unweighted_ problem is greedy while the _weighted_ one is DP.[^wis] It is the same failure as fractional versus 0/1 knapsack: weights destroy the greedy-choice property. $$ % caption: Weighted interval scheduling needs DP. Earliest-finish greedy would take the two % light intervals (gray, weight $1{+}1$) and reject the single heavy one (blue, % weight $5$); the optimum keeps the heavy interval. \begin{tikzpicture}[xscale=0.62, yscale=0.6, font=\small, light/.style={draw, thick, minimum height=5mm, fill=black!10}, heavy/.style={draw=acc, very thick, minimum height=5mm, fill=acc!18}] \definecolor{acc}{HTML}{2348F2} \node[light, minimum width=2.4cm] at (1.2,2) {$w{=}1$}; \node[light, minimum width=2.4cm] at (5.2,2) {$w{=}1$}; \node[heavy, minimum width=6cm] at (3.2,0.6) {$w{=}5$ (optimum)}; \draw[->, thick] (-0.2,-0.2) -- (7.2,-0.2) node[right, font=\footnotesize] {time}; \end{tikzpicture} $$ **Online interval scheduling.** When intervals arrive one at a time and each must be accepted or rejected on the spot — a machine-reservation feed, say — no deterministic online algorithm can be competitive against the offline optimum in the worst case: an adversary reveals a short interval, and whether you take it or not it can follow with intervals that make the other choice far better, forcing an unbounded competitive ratio for arbitrary lengths.[^online-sched] Restricting interval lengths or admitting randomization restores bounded ratios, which is why real reservation systems either batch requests (recovering the offline sort) or accept a provable approximation. The $O(n\log n)$ greedy of this lesson depends on seeing the whole instance at once. ## Takeaways - **Interval scheduling** maximizes compatible jobs by **earliest finish first**; a stays-ahead exchange argument proves optimality, in $\O(n\log n)$. - **Interval partitioning** minimizes machines by **earliest start first** with a min-heap of free times; the answer equals the **maximum depth** $d$, since depth forces $\ge d$ machines and greedy never opens more. - **Minimizing maximum lateness** on one machine uses **earliest deadline first**; an adjacent-swap exchange argument shows removing inversions never raises $L$. - All three are the same **sort-then-scan** skeleton: the entire design decision is the **sort key** (finish, start, or deadline), and the proof is a short exchange argument. [^clrs-activity]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.1): activity selection by earliest finish time and the structure of single-machine scheduling. [^skiena-sched]: **Skiena**, § — Scheduling: interval partitioning / coloring and the equivalence of minimum machines with maximum overlap depth. [^erickson-greedy]: **Erickson**, Ch. — Greedy Algorithms: greedy scheduling proofs by exchange arguments and the sort-key-is-the-algorithm framing. [^wis]: **Kleinberg, J. & Tardos, É.** (2005), _Algorithm Design_, Ch. 6 — Dynamic Programming (§6.1): weighted interval scheduling solved by the $\mathrm{OPT}(i)=\max\{w_i+\mathrm{OPT}(p(i)),\ \mathrm{OPT}(i-1)\}$ recurrence, the standard example that adding weights turns a greedy problem into a DP one. [^online-sched]: **Borodin, A. & El-Yaniv, R.** (1998), _Online Computation and Competitive Analysis_, Cambridge University Press — the competitive-analysis framework and lower bounds showing deterministic online interval scheduling has no bounded competitive ratio for arbitrary interval lengths.