1. Interval Scheduling

The interval scheduling maximisation problem (ISMP) asks: given a set of \(n\) requests, each occupying a time interval \(s_i\) and \(f_i\), left close - right open, select the largest subset of compatible (non-overlapping) requests. It is the prototypical problem solved by a greedy algorithm with an exchange argument. A rigorous proof technique that shows no other feasible solution can do strictly better Kleinberg (2006) ¹ and Cormen (2022) ².

Interval scheduling arises in CPU job scheduling, conference room booking, bandwidth allocation, genomic interval analysis, and many other resource-assignment contexts.

1.1 Problem Statement

Given \(n\) intervals \(I_i = [s_i, f_i)\) for \(i = 1, \ldots, n\) with \(s_i < f_i\), find a largest subset \(S \subseteq \{1, \ldots, n\}\) such that no two intervals in \(S\) overlap.

Two intervals \(I_i\) and \(I_j\) are compatible if \(f_i \leq s_j\) or \(f_j \leq s_i\).

1.2 Greedy Algorithm: Earliest Finish Time

The key insight is that always choosing the compatible interval with the smallest finish time never prevents selecting more intervals later — it leaves as much future time available as possible.

INTERVAL-SCHEDULE(intervals):
  sort intervals by finish time f_i (ascending)
  selected = []
  last_finish = -∞
  for each interval i in sorted order:
    if s_i ≥ last_finish:
      selected.append(i)
      last_finish = f_i
  return selected

Time complexity: \(O(n \log n)\) dominated by sorting; the greedy scan is \(O(n)\).

1.3 Correctness: Exchange Argument

Let \(A = \{a_1, a_2, \ldots, a_k\}\) be the greedy solution sorted by finish time, and let \(O = \{o_1, o_2, \ldots, o_m\}\) be any optimal solution sorted by finish time. We prove \(k = m\), i.e. the greedy solution is also optimal.

Lemma (Greedy stays ahead): For each \(r \leq k\), \(f(a_r) \leq f(o_r)\).

Proof by induction on \(r\).

Base case \(r = 1\): \(a_1\) has the smallest finish time of all intervals, so \(f(a_1) \leq f(o_1)\).

Inductive step: Assume \(f(a_{r-1}) \leq f(o_{r-1})\). Since \(O\) is feasible, \(s(o_r) \geq f(o_{r-1}) \geq f(a_{r-1})\). So \(o_r\) is compatible with last_finish \(= f(a_{r-1})\), meaning the greedy algorithm had \(o_r\) as a candidate when selecting \(a_r\). Since greedy chose \(a_r\), it must be that \(f(a_r) \leq f(o_r)\). \(\square\)

Theorem: Greedy produces an optimal solution, i.e. \(k = m\).

Proof by contradiction: Suppose \(k < m\). By the lemma applied at \(r = k\), \(f(a_k) \leq f(o_k)\). Since \(m > k\), \(o_{k+1}\) exists in \(O\). It must satisfy \(s(o_{k+1}) \geq f(o_k) \geq f(a_k)\), so \(o_{k+1}\) is compatible with the greedy selection at step \(k\). But then greedy would have selected at least one more interval after \(a_k\), contradicting \(k\) being the total. Contradiction. \(\square\)

1.4 Variants

1.4.1 Interval Scheduling Maximisation (weighted)

If each interval carries a weight \(v_i\) and the goal is to maximise total weight \(\sum_{i \in S} v_i\), the greedy approach breaks. The weighted version is solved in \(O(n \log n)\) by dynamic programming with binary search:

Let \(p(i)\) be the largest index \(j < i\) (sorted by finish time) such that \(I_j\) is compatible with \(I_i\). Then:

\(p(i)\) can be found with binary search in \(O(\log n)\), giving \(O(n \log n)\) total.

1.4.2 Interval Partitioning

A related problem: partition of all \(n\) intervals into the minimum number of groups such that no two intervals in the same group overlap. This equals the depth — the maximum number of intervals active at any one time — and is solved greedily by assigning each interval to any available group (or opening a new one) in \(O(n \log n)\) ¹.

1.4.3 Interval Colouring / Resource Allocation

For \(d\) resources, the maximum number of compatible intervals schedulable across all \(d\) resources is found by running the greedy \(d\) times or equivalently by an augmented earliest-finish scan.

1.5 Complexity Summary

1.6 Interactive Demo

The canvas below animates the earliest-finish-time greedy on a small instance. Intervals are sorted by finish time; each step evaluates the next interval (gold), adds it to the selection (green) or rejects it (red).