Earliest-Finish-First for Interval Scheduling

A single resource can serve one booking at a time. Each request is an interval with a start and an end, and two requests conflict if their intervals overlap. The task is to accept the largest possible number of requests. This is the interval scheduling problem, and it has a greedy solution that runs in $O(n \log n)$ and is optimal, which is unusual enough to be worth dissecting: several natural greedy rules for the problem are wrong, and the one that works is not the first one usually tried.

Three plausible rules, two of them wrong

Consider the rules a reasonable person would propose.

Earliest start first. Sort by start time and accept every interval that begins after the previous accepted one ended. This fails on an instance with one long interval starting at time 0 and ending at 100, and several short intervals occupying the same span in sequence. The rule takes the long interval first and accepts one request; the optimum accepts all the short ones.

Shortest interval first. Sort by duration and accept greedily. This fails on an instance with two long intervals that do not overlap each other and a shorter interval that overlaps both, bridging the gap between them. Taking the short one first blocks both long ones, giving one request where two are possible.

Earliest finish first. Sort by end time and accept every interval whose start is at or after the end of the last accepted interval. This one is optimal, and the reason is not that finishing early leaves more room in some vague sense. It is that the first-finishing interval is always safe to accept, in the precise sense of the exchange argument: some optimal solution contains it.

The proof, as a single exchange

Let the intervals be sorted so that $f_1 \le f_2 \le \dots \le f_n$, where $f_i$ is the finish time of interval $i$. Let $g$ be the interval with the earliest finish among all intervals, so $f_g \le f_i$ for every $i$.

Let $O$ be a maximum set of pairwise non-overlapping intervals, and let $o$ be the member of $O$ with the earliest finish. Because $g$ has the earliest finish of any interval in the input, $f_g \le f_o$.

Now form $O’ = (O \setminus {o}) \cup {g}$. Feasibility: every interval in $O$ other than $o$ starts at or after $f_o$, since $O$ is non-overlapping and $o$ is its earliest-finishing member. Because $f_g \le f_o$, every such interval also starts at or after $f_g$, so $g$ does not conflict with any of them. And $|O’| = |O|$, so $O’$ is maximum and contains $g$.

The greedy choice is therefore safe. After accepting $g$, the remaining problem is interval scheduling on the intervals that start at or after $f_g$, which is the same problem on a subset of the input. Induction on the number of intervals gives optimality. Note what the argument did not need: it did not need $g$ to be the only earliest-finishing interval, so ties are harmless. Any tie-breaking rule gives an optimal answer, though different optimal sets.

The proof also explains why the two rejected rules fail. For earliest start, the analogous claim would be “some optimal solution contains the earliest-starting interval”, and the long-interval example is a direct counterexample. For shortest duration, the claim “some optimal solution contains the shortest interval” is false for the bridging example. The failure is always at the same joint: the repair step cannot restore feasibility or cannot preserve cardinality.

Implementation and the comparison it depends on

def max_compatible(intervals):
    # intervals: list of (start, end), half-open [start, end)
    intervals = sorted(intervals, key=lambda iv: iv[1])
    chosen = []
    last_end = None
    for start, end in intervals:
        if last_end is None or start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

The sort dominates: $O(n \log n)$ comparisons, then a single $O(n)$ scan that makes one comparison per interval. The scan is a fold, not a search; no backtracking and no auxiliary structure beyond the output.

The interval convention matters more than it appears to. With half-open intervals $[s, e)$, two intervals where one ends exactly when the next begins do not conflict, and the test is start >= last_end. With closed intervals $[s, e]$, an interval ending at 5 and one starting at 5 do conflict at the single point 5, and the test becomes start > last_end. Mixing conventions between the sort key and the acceptance test produces off-by-one acceptances that are hard to see in testing because they only appear on touching endpoints. Timestamp granularity introduces the same issue in a different form: if times are stored in whole seconds and an event at 10:00:00.400 is recorded as second 10, two intervals can appear to touch when they do not.

Zero-length intervals need a decision as well. Under the half-open convention, a zero-length interval $[5,5)$ is empty and can always be accepted, which inflates the count without consuming any resource. Under the closed convention it occupies the instant 5. Either treatment can be defended, but the algorithm must be consistent, and the proof’s feasibility step must use the same convention as the code.

What the greedy structure buys beyond the count

The same sweep answers related questions about the interval set, because it processes intervals in order of finish time.

Maximum utilization with a fixed number of resources. Given $k$ identical resources, the greedy rule “assign each interval, in order of start time, to any free resource” uses exactly as many resources as the maximum number of intervals overlapping at a single point. That maximum is a lower bound, since those intervals pairwise conflict, and the greedy assignment attains it. The number of resources needed is therefore computable in $O(n \log n)$ by a sweep over endpoints, and this is the interval graph colouring problem: interval graphs are perfect, and the chromatic number equals the clique number.

A maximum independent set in an interval graph. The accepted intervals are exactly a maximum independent set of the interval graph whose vertices are intervals and whose edges are overlaps. On general graphs this problem is NP-hard; on interval graphs it is this greedy scan. The structure of the graph, not the cleverness of the rule, is what makes it tractable, and matroid greedy optimality marks the boundary of the explanation: the family of pairwise disjoint intervals is not a matroid, since one long interval can block several short ones and the exchange axiom for independent sets fails, so the matroid theorem does not apply even though the greedy scan is optimal.

Tie-breaking does not change the count. Different tie-breaks among intervals with equal finish times yield different accepted sets, but the exchange argument above never assumes the choice is unique, so all of them have the same maximum size. That makes the count a usable check on an implementation: two versions that break ties differently must return the same cardinality, and if they do not, at least one has a bug.

Where the rule stops working

The moment intervals carry weights, the greedy rule breaks. If each accepted interval contributes a value $w_i$ and the goal is to maximize total value rather than count, earliest-finish-first can be arbitrarily bad: one long interval worth a large amount may be displaced by many short intervals worth little. Weighted interval scheduling requires comparing, for each interval, the best solution that includes it against the best that excludes it, with the “previous compatible interval” found by binary search. That is a dynamic program over the sorted order, not a greedy scan, and the loss of the greedy property is exactly the loss of the exchange: replacing the earliest-finishing interval in an optimal weighted solution can destroy more value than it restores.

Precedence constraints break it too. If accepting an interval requires that some other interval also be accepted, the problem becomes a scheduling problem with release times and precedence, and the simple sweep has no way to look ahead. The same is true when the resource is not a single timeline but several machines with different availability, or when intervals must be assigned to specific rooms.

A different failure is subtler: the greedy scan assumes all intervals are known. In an online setting where intervals arrive in arbitrary order and must be accepted or rejected on arrival, earliest-finish-first is unavailable because it requires the whole input. Greedy by start time is the natural online rule, and its competitive ratio is not 1; the analysis of such ratios is a separate line of work from the offline optimum proved above.

Why the sweep generalizes: the interval order

The underlying reason the algorithm works is that intervals, ordered by finish time, form a structure in which “greedy by earliest deadline” is always safe. The same ordering appears in scheduling to minimize the maximum lateness, where the optimal rule is earliest deadline first, and in Moore and Hodgson’s algorithm for minimizing the number of late jobs on one machine, which orders jobs by deadline and, whenever a job finishes late, discards the scheduled job with the longest processing time. In each case the exchange has the same shape: the item with the earliest deadline can be moved to the front of an optimal schedule without violating feasibility, because everything it could conflict with finishes later.

What differs is the constraint that the exchange must respect. For interval scheduling it is non-overlap; for single-machine scheduling it is the machine’s capacity over time; for set cover it is coverage, and there the exchange fails outright, which is why the greedy algorithm for that problem needs a ratio guarantee instead of an optimality proof.