Scheduling & Interval Partitioning

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 zooms out to the whole family of interval and scheduling problems that the greedy method solves, and they turn out to be nearly the same algorithm wearing different hats. What separates them is which key you sort by. Sort by finish time and you maximize how many jobs fit; sort by start time and you minimize how many machines you need; sort by deadline and you 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.¹

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 the algorithm runs in $O (n log n)$ .

The picture is one of greedy never falling 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 to come.

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.

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.

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.²

The right invariant is depth. Define the depth at a point $t$ as the number of intervals containing $t$ , and let $d = max_{t} depth (t)$ be the maximum over all points. Depth is a hard lower bound on rooms, and greedy matches it.

colors needed = max overlap depth

d

(highlighted line crosses 3 intervals)

The greedy algorithm sorts by start time and keeps a min-heap 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:

\textsc{Partition}(I)

— fewest machines for intervals

I

1
sort $I$ by start time $s_i$ ascending
2
$H \gets$ empty min-heap of machines keyed by free time
3
for each interval $i$ in start order do
4
if $H$ nonempty and $\min(H).free \le s_i$ then
5
$m \gets \textsc{Extract-Min}(H)$
reuse earliest-freed machine
6
else
7
$m \gets$ new machine
none free: open one
8
$m.free \gets f_i$
9
$\textsc{Insert}(H, m)$
10
return $|H|$
total machines opened

Tracing the scan makes the rule concrete. 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 — and that very moment is a point of depth $3$ , the witness behind the lower bound.

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.

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.³ 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.

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 $ℓ_{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.¹

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. Those two qualifiers, no idle time and deadline order, are exactly what the proof needs.

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. $□$

an adjacent EDF swap: exchanging an inversion (

d_{i} > d_{j}

) never raises max lateness

So minimizing maximum lateness is, again, sort-and-scan: sort by deadline in $O (n log n)$ , run in that order, done. A small worked run makes the objective concrete: 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.

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

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.

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 $\geq 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, Ch. 16 — Greedy Algorithms (§16.1): activity selection by earliest finish time and the structure of single-machine scheduling. ↩ ↩²
Skiena, § — Scheduling: interval partitioning / coloring and the equivalence of minimum machines with maximum overlap depth. ↩
Erickson, Ch. — Greedy Algorithms: greedy scheduling proofs by exchange arguments and the sort-key-is-the-algorithm framing. ↩