GreedyAlgorithmaka earliest finish first, maximum non-overlapping activities

Activity Selection

Pick the maximum number of mutually compatible activities by repeatedly taking the one that finishes earliest.

Pattern: GreedyPractice (3)
Progress

Overview

Given n activities with start and finish times, choose the largest set such that no two overlap. The greedy rule is earliest finish time first: sort by finish, take the first activity, then repeatedly take the next activity whose start is at or after the finish of the last one taken.

This is the textbook example of the greedy-choice property: a locally optimal choice (finish as early as possible, leaving the most room) is part of some globally optimal solution, and after making it the remaining problem has the same form. It is the unweighted special case of Interval Scheduling; the weighted version needs Dynamic Programming.

greedyintervalsexchange argumentearliest finishsorting

Intuition

A mental model before the formal terms.

You want to attend as many talks as possible in one room. The talk that ends soonest frees you up earliest, so whatever you could have attended after any other first choice, you can still attend after this one. Ending early never costs you anything.

Sorting by start time or by duration feels natural but fails: a talk that starts first may run all day, and the shortest talk may sit in the middle and block two long ones on either side.

How it works

  1. Sort activities by finish time (ties: any order).
  2. Select the first activity; set lastFinish to its finish time.
  3. Scan the rest in order: if start ≥ lastFinish, select it and update lastFinish; otherwise skip.
  4. The selected list is a maximum-size compatible set.

Why it works

Exchange argument. Let a₁ be the activity with the earliest finish and let OPT be any optimal solution. OPT's first activity o₁ (in finish order) finishes no earlier than a₁, so replacing o₁ by a₁ keeps the set compatible (everything after o₁ starts at or after f(o₁) ≥ f(a₁)) and the same size. Hence some optimal solution begins with a₁.

Optimal substructure. After choosing a₁, the remaining activities compatible with it form an instance of the same problem, and an optimal solution to the original is a₁ plus an optimal solution to the remainder. Induction on n completes the proof.

Sorting by finish time is what makes "compatible with a₁" equal to "starts at or after f(a₁)", which the single scan checks in O(1) per activity.

Recognition

How to tell a problem wants this.

  • "Maximum number of non-overlapping intervals / meetings / tasks" with one resource.
  • "Minimum number of intervals to remove so the rest do not overlap" — the complement of this problem.
  • Unit weights: every interval counts equally. If intervals have values, greedy breaks and you need DP.
“maximum number of non-overlapping” → Greedy“overlapping intervals” → Intervals

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1sort activities by finish
2chosen = [a[0]]; lastFinish = a[0].finish
3for act in a[1:]:
4  if act.start >= lastFinish:
5    chosen.push(act); lastFinish = act.finish
6return chosen

Implementations

1from typing import NamedTuple
2 
3# Activity selection: given intervals, choose the largest set that do not
4# overlap. The greedy is "always take the activity that FINISHES earliest
5# among those still compatible" — earliest finish leaves the most room.
6# PRECONDITION: every activity has positive duration (start < finish).
7# Zero-length activities break the optimality proof — see the walkthrough.
8 
9 
10class Activity(NamedTuple):
11    start: int
12    finish: int
13 
14 
151 · Sort by finish time; that single ordering is the whole algorithm
16def select_activities(acts: list[Activity]) -> list[int]:
17    idx = sorted(range(len(acts)), key=lambda i: acts[i].finish)
18 
192 · Sweep: take an activity whenever it starts at or after the last finish
20    chosen: list[int] = []
21    last_finish = float("-inf")
22    for i in idx:
23        if acts[i].start >= last_finish:
24            chosen.append(i)
25            last_finish = acts[i].finish
26    return chosen
27 
28 
293 · Count only — the same sweep without recording indices
30def max_activities(acts: list[Activity]) -> int:
31    count = 0
32    last_finish = float("-inf")
33    for a in sorted(acts, key=lambda x: x.finish):
34        if a.start >= last_finish:
35            count += 1
36            last_finish = a.finish
37    return count
38 
39 
404 · Why earliest-finish and not earliest-start or shortest-duration:
41# sorting by START fails on [0,10],[1,2],[3,4] (takes 1, optimum is 2)
42# sorting by DURATION fails on [0,5],[4,6],[5,10] (takes 1, optimum is 2)
43def max_activities_by_start(acts: list[Activity]) -> int:
44    count = 0
45    last_finish = float("-inf")
46    for a in sorted(acts, key=lambda x: x.start):
47        if a.start >= last_finish:
48            count += 1
49            last_finish = a.finish
50    return count  # NOT optimal — included to show the failure
51 
52 
535 · The exchange argument: if an optimal solution's first activity finishes
54# later than the greedy's, swapping in the greedy one keeps every later choice
55# valid (it frees at least as much room) and keeps the count the same.
56def compatible(a: Activity, b: Activity) -> bool:
57    return a.finish <= b.start or b.finish <= a.start
Walkthrough
  1. sorted(range(len(acts)), key=lambda i: acts[i].finish) produces the index permutation in one expression.
  2. Activity(NamedTuple) gives an immutable record with named fields, __eq__ and __repr__ for three lines.
  3. float("-inf") is the initial sentinel; because Activity fields are ints, the comparison is int-to-float, which Python handles exactly for any realistic magnitude. The start < finish precondition is not enforced — a __post_init__ check on a dataclass would catch it, which NamedTuple cannot do.
  4. sorted(acts, key=...) returns a new list, so the counting variants never mutate the caller's data.
  5. Both the correct and the incorrect key are present, differing by one word — which is exactly how close the mistake is in practice.
Complexity (this implementation)
time O(n log n) · space O(n)
Language notes
  • sorted(key=...) computes the key once per element and is stable, so ties keep input order.
  • operator.attrgetter("finish") is a marginally faster key than a lambda for large inputs.
  • Because Activity is a NamedTuple, sorted(acts) without a key would order by (start, finish) — plausible-looking and wrong.
  • math.inf and float("-inf") are the same value; the latter reads more explicitly at a single use site.
Common mistakes in this language
  • Calling sorted(acts) with no key and getting start-time order by accident, since NamedTuple compares field by field.
  • Sorting by start or by duration.
  • Using acts.sort() and mutating the caller's list.
  • Feeding in zero-length activities, which violate the precondition and make the greedy silently non-optimal.
Language differences that matter here
  • Sort stability differs: Python and JS/TS sorts are stable, so ties in finish time keep input order; C++ std::sort is not, and the chosen indices can vary between runs.
  • A NamedTuple in Python compares field-by-field, so sorted(acts) silently sorts by start — a trap the C++ struct and the TypeScript interface do not have, because neither is ordered by default.
  • Index-permutation sorting is the same idiom everywhere, but only Python expresses it in one line (sorted(range(n), key=...)).
  • JavaScript again needs an explicit comparator even when sorting plain integer indices, or it orders them lexicographically.

Complexity

Best
O(n)
Average
O(n log n)
Worst
O(n log n)
Space
O(1)

Dominated by sorting; O(n) if input is already sorted by finish time. Output list excluded from space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Maximizing the count of compatible intervals on a single resource.
  • Minimum removals to make intervals non-overlapping (answer = n − maxCompatible).
  • As the first pass before a weighted or multi-resource generalization.
Avoid it when
  • Weighted intervals: activities A=[0,10] weight 10, B=[0,3] weight 1, C=[4,10] weight 1. Earliest-finish picks B then C for total 2; the optimum is A alone with 10. Use weighted Interval Scheduling DP.
  • Multiple rooms (minimum number of resources to host all activities) — that is Merge Intervals-style sweep or a Priority Queue of end times (Meeting Rooms II), not selection.
  • Sorting by start time or shortest duration: [1,100], [2,3], [4,5] — start-first takes the long one and gets 1; earliest-finish gets 2.

Alternatives

Interval SchedulingMerge IntervalsInterval (Range) DP
Compare: Greedy vs Dynamic Programming

Common mistakes

  • Sorting by start time instead of finish time.
  • Using start > lastFinish when touching endpoints are allowed (or vice versa) — read the problem's definition of overlap.
  • Forgetting to sort at all and greedily scanning input order.
  • Applying the rule to weighted instances.

Interview patterns

  • Non-overlapping Intervals (LeetCode 435): count kept intervals with earliest-finish, return n − kept.
  • Minimum Number of Arrows to Burst Balloons: same greedy, counting groups.
  • Maximum Length of Pair Chain: earliest-finish on pairs.
Interview questions on this
Mock interviews

Example problems

Meeting Rooms IImediumNon-overlapping IntervalsmediumActivity Selectioneasy