Scheduling to Fit the Most Jobs

The problem: you're given a list of jobs, each with a fixed start time and end time, and a single machine (or meeting room, or trading desk) that can only run one job at a time. You want to accept as many jobs as possible, but any two accepted jobs must not overlap in time. Which jobs do you pick? This is the interval scheduling puzzle, and the tempting-but-wrong instincts — pick the shortest jobs first, or pick the jobs that start earliest — both fail on simple counterexamples. The rule that actually works is picking by earliest finish time.

The rule: always take the job that finishes earliest

Sort all jobs by their end time. Go through them in that order, and whenever a job doesn't overlap with the last job you accepted, accept it. That's the whole algorithm. The reasoning: whichever job finishes first among all your options leaves the most room on the timeline for everything after it, so committing to it can never cost you more future options than committing to any other available job would.

Why "shortest job" and "earliest start" both fail

Picking the shortest job first seems intuitively efficient, but a short job can sit right in the middle of the day and block two much longer non-overlapping jobs on either side of it — one short pick can cost you two good ones. Picking by earliest start fails too: a job that starts very early can also run very long, blocking everything after it, while a job that starts a bit later but finishes quickly frees up the rest of the day. Earliest finish time is the only one of the three natural rules that survives an exchange-argument proof of optimality.

Worked example: six candidate jobs

Jobs given as (start, end): $A(1,4)$, $B(3,5)$, $C(0,6)$, $D(5,7)$, $E(3,9)$, $F(6,10)$, $G(8,11)$. Sort by finish time: $A(1,4)$, $B(3,5)$, $D(5,7)$, $C(0,6)$, $F(6,10)$, $E(3,9)$, $G(8,11)$ — reordering strictly by end time gives $A(4), B(5), D(7), C(6), F(10), E(9), G(11)$, so sorted: $A(1,4), B(3,5), C(0,6), D(5,7), F(6,10), E(3,9), G(8,11)$.

Walk through in that order: take $A(1,4)$ — first pick, last end is now 4. $B(3,5)$ starts at 3, before 4 — overlaps, skip. $C(0,6)$ starts at 0 — overlaps, skip. $D(5,7)$ starts at 5, after 4 — take it, last end is now 7. $F(6,10)$ starts at 6 — overlaps, skip. $E(3,9)$ starts at 3 — overlaps, skip. $G(8,11)$ starts at 8, after 7 — take it. Final schedule: $A, D, G$ — three jobs, and no other combination of these seven jobs fits four or more without an overlap, which you can verify by checking that every job not chosen genuinely conflicts with the running selection at the point it was considered.

What this means in practice

This puzzle shows up directly in resource booking (meeting rooms, trading desks, exchange colocation slots) and indirectly anywhere you're choosing a maximal non-conflicting subset from overlapping candidates, including selecting a set of non-overlapping backtest windows or non-overlapping trade holding periods for an event study. The pattern to recognize: whenever "maximize the count of accepted non-overlapping things" is the goal, earliest finish time is the rule to reach for first, and an exchange argument is how you'd defend it if pressed.