Greedy Algorithms

A greedy algorithm builds an answer one step at a time, always grabbing the choice that looks best right now and never reconsidering. It is the simplest strategy there is — no backtracking, no tables. The catch: a locally best choice is not always globally best, so greedy only works when the problem has the right shape. Activity selection is the classic example where it does.

Intuition

Imagine a single meeting room and a stack of booking requests. You want to host as many meetings as possible. Which one should you accept first? Not the one that starts earliest, and not the shortest — the one that finishes earliest. Finishing early frees the room sooner, leaving the most time for everything else. Accept it, then repeat with the next request that starts after the room is free. That single instinct — "always free the room as soon as possible" — is the whole algorithm.

Walk through it

On the right, five activities A–E are drawn as bars on a shared timeline, already sorted by finish time. A vertical cutoff line tracks last_end, the finish time of the most recent activity we took; it starts at 0.

We sweep left to right. A (1,3) starts at 1 ≥ 0, so we take it (it turns green) and the cutoff jumps to 3. B (2,5) starts at 2, which is before 3 — it overlaps A, so it dims out. C (4,7) starts at 4 ≥ 3: take it, cutoff moves to 7. D (6,9) starts at 6 < 7, skip. E (8,10) starts at 8 ≥ 7: take it. The three green bars — (1,3), (4,7), (8,10) — are the answer, and no set of four non-overlapping activities exists.

The code, line by line

def select(activities):
    activities.sort(key=lambda a: a[1])  # by finish time
    chosen = []
    last_end = 0
    for start, end in activities:
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

• Line 2 is the greedy choice: sort by a[1], the finish time. Everything downstream depends on this order.
• Line 4 sets last_end = 0 so the very first activity is always eligible.
• Line 6 is the test: an activity is compatible only if it starts at or after last_end — i.e. it does not overlap the last one we took.
• Lines 7–8 commit the choice: record it and advance last_end to its finish time. That advance is the cutoff line sliding right in the animation.

The greedy-choice property is what makes this correct: taking the earliest-finishing activity is always part of some optimal solution, because any other first choice finishes no sooner and so leaves no more room. Once that first pick is fixed, the rest is the same problem on a smaller timeline — so repeating the greedy choice stays optimal.

Complexity

If the activities arrive already sorted, the whole thing is O(n) — just the one sweep. The extra space is O(1) beyond the output list: only last_end and a counter.

When to use / pitfalls

Practice