Given a set of activities, each occupying a start time and an end time on one shared resource — one meeting room, one machine, one person's calendar — pick the largest possible subset that never overlaps. Two activities overlap if one starts before the other finishes; back-to-back activities that touch exactly at the boundary (one starts the instant the other ends) don't count as overlapping. This is interval scheduling, one of the oldest problems greedy algorithms are taught on, because the correct rule is short and the wrong-looking-right rules are so tempting.
The greedy idea: sort every activity by its finish time, then walk the list once, taking each activity that starts at or after the finish time of whichever activity was taken most recently. That's the whole algorithm — no lookahead, no reconsidering an earlier choice, one pass. This is the site's second entry filed under Greedy, after Huffman Coding. All three of Cairn's other greedy entries — Huffman's priority-queue merges, Kruskal's globally sorted edge list, Prim's frontier growth — commit to whichever locally best option is available and never revisit that choice. Activity selection follows the same discipline with its own specific rule (sort by finish time) and its own specific proof of why that particular rule, and not some other equally plausible-sounding one, is the one that's actually guaranteed correct.
Type a list of start-end pairs (comma-separated), pick a greedy rule, and press
Load, then Step or Run. Each row is one activity,
ordered by whichever rule is selected — a green bar means accepted, a faded dashed bar means
rejected as overlapping, and the short accent tick on the row being decided marks the finish time of
the most recently accepted activity, the cutoff a new activity's start must clear. The demo also
brute-forces the true optimal count for comparison (capped at 12 activities so that stays instant),
so a rule that falls short is visible immediately, not just claimed.
timeline
The proof is an exchange argument. Claim: some optimal solution includes the activity that
finishes earliest of all, call it a. Take any optimal solution S; if it
already contains a, done. If not, look at whichever activity in S finishes
first, call it b — since a finishes earliest among all activities,
a finishes at or before b does. Swap b out for a:
every other activity in S already starts at or after b's finish time, and
a finishes no later than b, so none of them can conflict with
a either. The swap produces another solution, still optimal (same size), that does
contain a. Once a is fixed as a safe first choice, the rest of the problem
is identical in shape — pick the largest non-overlapping subset from whatever's left that starts at
or after a finishes — so the same argument applies again to that earliest
finisher, and so on. Sorting once and taking a single greedy pass is exactly this induction
unrolled.
On the default 11-activity set — the classic textbook example — earliest-finish-time greedy picks
activities 1 [1,4], 4 [5,7], 8 [8,11], and 11
[12,16]: 4 activities, confirmed by brute force to be the true optimum (no subset of 5
or more of these 11 activities is non-overlapping). The other two rules offered in the demo above
don't reach it — see Pitfalls.
function activitySelection(activities) {
// activities: [{ start, end }]
const sorted = [...activities].sort((a, b) => a.end - b.end);
const chosen = [];
let lastEnd = -Infinity;
for (const a of sorted) {
if (a.start >= lastEnd) {
chosen.push(a);
lastEnd = a.end;
}
}
return chosen;
}The greedy rule isn't interchangeable with other plausible-sounding rules. Switch
the demo's rule to earliest start time on the unchanged default data: it picks activity 3
[0,6] first because nothing starts earlier, which then blocks every short activity that
would otherwise have fit before time 6 (activities 1, 2, 5, 10 all rejected), and it ends with just 3
activities (3, 7, 11) where the brute-force optimum is 4 —
starting first says nothing about finishing soon, so an early-starting, slow-finishing activity can
block several shorter ones the finish-time rule would have caught. Shortest duration first
can fail too, though not on this particular dataset — paste in
9-11, 9-14, 5-10, 1-5, 8-13 and switch to that rule: it picks only 1 activity, where the
true optimum (also shown by the demo) is 2 ([1,5] then [9,11]). Both
counterexamples were found by brute-force search over randomized small instances, not hand-crafted to
look bad — checked, not just asserted. Only the earliest-finish-time rule has the exchange-argument
proof above backing it; the other two are simply different sort keys applied to the identical
accept-if-it-fits loop, and nothing about that loop makes them safe.
This maximizes count, not value. If every activity instead carried a weight — a room booking worth a different amount of revenue, say — and the goal became the highest-value non-overlapping subset rather than the largest-count one, this exact greedy rule stops being correct: a single high-value activity can be worth skipping several lower-value ones for, and finish time alone can't tell the two cases apart. That's weighted interval scheduling, solved instead by a dynamic-programming recurrence over activities sorted by finish time (similar in spirit to 0/1 Knapsack's recurrence) — see Weighted Interval Scheduling, which uses this exact page's own default dataset (with weights added) to show the divergence live.
Touching exactly at the boundary is allowed by convention, not by necessity. The
demo's accept condition is start ≥ lastEnd, so an activity that starts the exact
instant the previous one ends is accepted — checked directly: 0-3, 3-6, 6-9 all get
accepted back-to-back. That matches "one meeting room, zero changeover time." A resource that needs
real gap time between activities (a machine with a cooldown, a room needing cleaning) would need a
strict > instead, or an explicit changeover added to each end time before comparing —
a one-line change, but a real modeling decision this algorithm doesn't make for you.
Time: O(n log n), entirely the cost of the initial sort — the
single pass that follows is O(n), one comparison per activity against the running
cutoff. Space: O(n) for the sorted copy and the chosen list (or
O(1) extra if sorting in place and only counting, not reconstructing, the chosen set).
This demo's brute-force optimal-count check, shown purely for comparison, is O(2^n · n)
and capped at 12 activities for exactly that reason — nothing about the greedy algorithm itself needs
it.
See Choosing a Greedy Strategy for how this entry's proof compares against the site's other nine Greedy entries — short version: this is Tier 1, exact on every input, by a swap-in-the-earliest-finisher argument that the demo's other two sort keys (start time, duration) can't match.