Interval Scheduling: Why Earliest Finish Time Is the Right Greedy

Greedy algorithms have a reputation for being either obvious or wrong, and interval scheduling is the problem that shows why. There are several reasonable-sounding rules for picking which job to book next. Only one of them is correct, and a random test suite will not reliably tell you which.

This article tries the tempting rules, breaks them with small counterexamples, and then proves the right one — because for greedy algorithms, the proof is the part that matters.

The problem it solves

You have one room and a list of booking requests, each with a start and an end time. Two bookings clash if they overlap; a booking that starts exactly when another ends is fine. Accept as many bookings as possible.

It is the core of a family: the maximum number of non-overlapping intervals, the minimum number of intervals to remove so the rest do not overlap (that is n minus the answer here), and the minimum number of arrows to burst balloons laid out on a line.

The intuition

Every greedy rule for this problem has the same shape: sort the jobs by some key, walk through them, and take each one that does not clash with what you have already taken. The only decision is the key. Three candidates suggest themselves.

Earliest start. Take whatever begins first. It fails as soon as an early job is long: a booking from 0 to 6 blocks both 1-to-4 and 5-to-7, which could have been booked together.

Shortest duration. Short jobs use less of the day, so prefer them. It fails when a short job sits across the boundary of two longer ones: 4 to 7 is the shortest job in (0, 5), (4, 7), (6, 11), and taking it blocks both others.

Fewest conflicts. Prefer the job that clashes with the fewest others. This one sounds genuinely clever, and it survives far more tests than the other two. It still fails — the counterexample in the code below uses eleven jobs.

Earliest finish. Take whatever ends first. The intuition: the job that frees the room soonest leaves the most time for everything else. Unlike the other three, this one can be proved.

The exchange argument

Take any optimal schedule and look at its first job. The greedy's first job finishes no later — it was chosen for finishing earliest. So swap them: the rest of the optimal schedule started after the old first job ended, which is at or after the greedy's first job ends, so nothing clashes. The schedule is still valid and still the same size.

Now some optimal schedule begins with the greedy's choice. Remove that job and every job it clashes with, and the same argument applies to what is left. By induction, the greedy's picks can be swapped into an optimal schedule one at a time without ever shrinking it — so the greedy schedule is optimal.

The argument works only because "finishes earliest" is exactly the property the swap needs. Try the same swap with "starts earliest" and it breaks: the greedy's job might end later and collide with the second job.

Watch it run

The animation shows five requests on one day. It first applies the wrong rule — earliest start — and books the long 0-to-6 job, which blocks two others. Then the bars re-stack by finishing time and a sweep line walks left to right once, taking each job that starts at or after the last booked one ends.

The code

A generic greedy that takes jobs in any key order, the three rules on their counterexamples, and the eleven-job trap for fewest conflicts:

def overlaps(a, b):                     # touching ends, like (1, 4) and (4, 6), is fine
    return a[0] < b[1] and b[0] < a[1]

def greedy(jobs, key):                  # take jobs in key order whenever they fit
    taken = []
    for job in sorted(jobs, key=key):
        if not any(overlaps(job, t) for t in taken):
            taken.append(job)
    return sorted(taken)

by_start  = lambda j: j[0]
by_length = lambda j: j[1] - j[0]
by_finish = lambda j: j[1]

day = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 10)]
print(greedy(day, by_start))            # [(0, 6), (8, 10)]
print(greedy(day, by_finish))           # [(1, 4), (5, 7), (8, 10)]

short_trap = [(0, 5), (4, 7), (6, 11)]
print(greedy(short_trap, by_length))    # [(4, 7)]
print(greedy(short_trap, by_finish))    # [(0, 5), (6, 11)]

def fewest_conflicts(jobs):             # sounds clever, is still a guess
    left, taken = list(jobs), []
    while left:
        j = min(left, key=lambda a: (sum(overlaps(a, b) for b in left if b is not a), a[1]))
        taken.append(j)
        left = [b for b in left if b is not j and not overlaps(b, j)]
    return taken

row = [(0, 3), (3, 6), (6, 9), (9, 12)]           # four jobs that all fit
trap = row + [(5, 7)] + [(2, 4)] * 3 + [(8, 10)] * 3
print(len(fewest_conflicts(trap)), len(greedy(trap, by_finish)))   # 3 4

In the trap, the job from 5 to 7 clashes with only two others, so fewest-conflicts takes it first — and it knocks out two of the four jobs that could all have been booked.

The version you would actually write needs no overlap check against every booking: sorted by finish time, the last accepted job is the only one a new job can clash with. Below, it is checked against a brute force that tries every subset, and the three other rules are scored on the same random inputs:

import random
from itertools import combinations

def max_jobs(jobs):                     # the real thing: one sort, one pass
    count, last_end = 0, float("-inf")
    for s, e in sorted(jobs, key=lambda j: j[1]):
        if s >= last_end:
            count, last_end = count + 1, e
    return count

def brute(jobs):                        # largest subset with no overlapping pair
    for r in range(len(jobs), 0, -1):
        for pick in combinations(jobs, r):
            if not any(overlaps(a, b) for a, b in combinations(pick, 2)):
                return r
    return 0

random.seed(8)
ok, right = True, {"start": 0, "length": 0, "conflicts": 0}
for _ in range(3000):
    jobs = []
    for _ in range(random.randint(0, 9)):
        s = random.randint(0, 15)
        jobs.append((s, s + random.randint(1, 6)))
    best = brute(jobs)
    ok &= max_jobs(jobs) == len(greedy(jobs, by_finish)) == best
    right["start"] += len(greedy(jobs, by_start)) == best
    right["length"] += len(greedy(jobs, by_length)) == best
    right["conflicts"] += len(fewest_conflicts(jobs)) == best
print(ok, right)
# True {'start': 2599, 'length': 2939, 'conflicts': 3000}

Read that last line carefully. Earliest finish matches the brute force every time. Shortest-first is right on 2,939 of 3,000 random inputs, which is enough to pass a casual test suite. And fewest-conflicts is right on all 3,000 — yet the eleven-job trap above proves it wrong. Random testing is good at catching bugs in a correct idea; it is weak evidence that a greedy idea is correct. That is what the exchange argument is for.

The complexity

Sorting is O(n log n); the sweep is one pass with constant work per job. Total O(n log n) time and O(1) extra beyond the sort. If the jobs arrive already sorted by end time, it is O(n).

Where it goes wrong

• Sorting by start. The most common mistake, because interval merging sorts by start. Different problem, different key.
• Strict versus non-strict comparison. s >= last_end lets a job start the moment the previous one ends. If the problem says touching intervals overlap, use >.
• Answering the wrong question. Maximising bookings in one room is this problem. Finding how many rooms you need for all of them is a different one: see meeting rooms.
• Weights. If each job has a value and you want the most value, not the most jobs, no sort order works in general, and the answer is dynamic programming over jobs sorted by end.

How to say it in an interview

"I sort by end time and take every job that starts at or after the last one I took. It's optimal by an exchange argument: in any optimal schedule I can swap its first job for the one that ends earliest without causing a clash, then repeat on the rest. That's O(n log n) for the sort. Sorting by start or by length both have small counterexamples."

Offer the counterexample for earliest start before you are asked. It shows you chose the key, rather than remembered it.