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 covers the whole family of interval and scheduling problems that 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.¹

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 $\mathbb{O}(n\log n)$.

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.

For example, take five requests for one machine, already sorted by finish time:

Scanning in finish order and keeping $f_{\text{last}}$, the finish of the most recently accepted interval:

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 $\mathbb{O}(n\log n)$. Everything below reuses this skeleton (sort, scan, exchange-argument proof) with a different key and a different objective.

from typing import NamedTuple, Sequence

class Interval(NamedTuple):
  """
    A half-open interval [start, finish); two intervals are compatible\n
    when they do not overlap (one's start is at or after the other's finish).\n
  """
  start: float
  finish: float

def schedule_intervals(intervals: Sequence[Interval]) -> list[Interval]:
  """
    A maximum-size subset of `intervals` that are pairwise compatible,\n
    chosen by earliest finish time. Returns them in finish-time order.\n
  """
  by_finish: list[Interval] = sorted(intervals, key=lambda item: item.finish)
  chosen: list[Interval] = []
  last_finish: float = float("-inf")

  # take each interval only if it starts at or after the last chosen finish.
  for interval in by_finish:
    if interval.start >= last_finish:
      chosen.append(interval)
      last_finish = interval.finish

  return chosen

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\text{depth}(t)$ be the maximum over all points. Depth is a hard lower bound on rooms, and greedy matches it.

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.

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.

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.

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

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 $\mathbb{O}(n\log n)$ and each interval does $\mathbb{O}(\log n)$ heap work, for $\mathbb{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.

import heapq
from typing import NamedTuple, Sequence

class Interval(NamedTuple):
  """
    A half-open interval [start, finish) to be assigned to a machine.\n
  """
  start: float
  finish: float

class Machine:
  """
    One machine (room, color) with the half-open intervals assigned to it,\n
    in the order they were placed.\n
  """

  def __init__(self) -> None:
    self.intervals: list[Interval] = []

  @property
  def free_at(self) -> float:
    """
      The time this machine next becomes free — the finish of its last\n
      interval, or -infinity when it is still empty.\n
    """
    if not self.intervals:
      return float("-inf")
    return self.intervals[-1].finish

  def assign(self, interval: Interval) -> None:
    """
      Place `interval` on this machine.\n
    """
    self.intervals.append(interval)

def partition_intervals(intervals: Sequence[Interval]) -> list[Machine]:
  """
    Assign every interval to a machine so that no machine holds two\n
    overlapping intervals, using the fewest machines. The number of\n
    machines returned equals the maximum overlap depth.\n
  """
  by_start: list[Interval] = sorted(intervals, key=lambda item: item.start)
  machines: list[Machine] = []

  # heap of (free_time, insertion_index, machine); index breaks ties so two
  # equally-free machines never compare Machine objects.
  available: list[tuple[float, int, Machine]] = []

  for interval in by_start:

    # reuse the earliest-freed machine if it is free, else open a new one.
    if available and available[0][0] <= interval.start:
      _, order, machine = heapq.heappop(available)
    else:
      machine = Machine()
      order = len(machines)
      machines.append(machine)

    # place the interval and re-queue the machine keyed by its new free time.
    machine.assign(interval)
    heapq.heappush(available, (interval.finish, order, machine))

  return machines

def minimum_machines(intervals: Sequence[Interval]) -> int:
  """
    The fewest machines needed — equivalently, the maximum overlap depth.\n
  """
  return len(partition_intervals(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 ${\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.¹

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.

So minimizing maximum lateness is, again, sort-and-scan: sort by deadline in $\mathbb{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.

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.

from typing import NamedTuple, Sequence

class Job(NamedTuple):
  """
    One job: how long it runs and the deadline it should finish by.\n
  """
  name: str
  processing_time: float
  deadline: float

class ScheduledJob(NamedTuple):
  """
    A job placed in the schedule: its finish time and resulting lateness.\n
  """
  job: Job
  finish: float
  lateness: float

def minimize_max_lateness(jobs: Sequence[Job]) -> list[ScheduledJob]:
  """
    Order `jobs` by earliest deadline first and run them with no idle gaps,\n
    returning each job's finish time and lateness in run order. This order\n
    minimizes the maximum lateness across all jobs.\n
  """
  by_deadline: list[Job] = sorted(jobs, key=lambda item: item.deadline)
  schedule: list[ScheduledJob] = []
  finish: float = 0.0

  # run jobs back-to-back, recording each finish time and its lateness.
  for job in by_deadline:
    finish += job.processing_time
    lateness: float = max(0.0, finish - job.deadline)
    schedule.append(ScheduledJob(job, finish, lateness))

  return schedule

def max_lateness(jobs: Sequence[Job]) -> float:
  """
    The minimum achievable maximum lateness for `jobs`. Empty input has\n
    lateness 0.\n
  """
  schedule: list[ScheduledJob] = minimize_max_lateness(jobs)
  if not schedule:
    return 0.0
  return max(entry.lateness for entry in schedule)

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:

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.⁴ It is the same failure as fractional versus 0/1 knapsack: weights destroy the greedy-choice property.

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.⁵ 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 $\mathbb{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.