Greedy Algorithms and Exchange Arguments

A greedy algorithm takes the option that looks best right now and never takes it back. No search tree, no memo table, no backtracking — one pass, one decision per step.

The trouble is that a wrong greedy algorithm does not crash. It returns a reasonable-looking answer that is simply not the best one, and nothing in the output tells you so. This is why interviewers care much less about whether you can write the greedy loop and much more about whether you can say out loud why the local choice is safe.

The shape of a greedy algorithm

Almost every greedy solution has the same three parts: a sort key that makes the right choice obvious (choosing this key is the algorithm), a feasibility check that accepts the next item if it does not break anything already committed, and a commitment that is never revisited.

Because the sort dominates, the cost is nearly always $O(n \log n)$ time plus an $O(n)$ single scan, with $O(1)$ extra space beyond the sort. Compare that with the $O(n^2)$ or $O(nW)$ table a dynamic program for the same problem would build. Greedy is what you reach for when a DP solution exists but is too slow or too memory-hungry.

Worked example: fitting the most meetings into a morning

You have six requests for one room and you want to accept as many as possible. Duration and importance do not matter — only the count.

	Start	End
A	9:00	10:30
B	9:30	11:00
C	10:00	10:45
D	10:45	12:00
E	11:30	12:30
F	12:15	13:00

The key is to sort by earliest finishing time, not earliest start and not shortest duration. Finishing early is the only thing that matters, because the room becomes free sooner and every remaining option stays on the table.

Sorted by end time: A (10:30), C (10:45), B (11:00), D (12:00), E (12:30), F (13:00). Now walk the list, tracking the time the room frees up:

• A — room is free, take it. Room free at 10:30.
• C starts 10:00, before 10:30. Skip.
• B starts 9:30, before 10:30. Skip.
• D starts 10:45, after 10:30. Take it. Room free at 12:00.
• E starts 11:30, before 12:00. Skip.
• F starts 12:15, after 12:00. Take it.

Answer: A, D, F — three meetings. Brute force over all 63 non-empty subsets agrees that three is the maximum.

def max_meetings(intervals):        # O(n log n) sort + O(n) scan, O(1) extra
    intervals.sort(key=lambda iv: iv[1])   # by END time
    free_at, chosen = float("-inf"), []
    for start, end in intervals:
        if start >= free_at:               # feasible: no overlap
            chosen.append((start, end))    # commit, never revisit
            free_at = end
    return chosen

Two plausible alternative keys fail. Earliest start loses to one meeting running 9:00–13:00 that blocks everything. Shortest duration loses on 9:00–11:00, 10:45–11:15, 11:00–13:00: it grabs the 30-minute middle meeting, which collides with both neighbours, returning one where two were available.

Why it works: the exchange argument

Take any optimal schedule and list its meetings in time order. Call its first meeting $o_1$ and the greedy first pick $g_1$. By construction $g_1$ finishes no later than $o_1$, because greedy scanned everything and took the earliest finisher. So swap $o_1$ for $g_1$: the schedule is still conflict-free (the room frees up no later than before) and still has the same number of meetings, so it is still optimal. Repeat on the second slot, the third, and so on. Every optimal solution can be edited step by step into the greedy one without ever losing a meeting — so greedy is optimal too.

That is an exchange argument. Its close cousin is "greedy stays ahead", where you prove by induction that after $k$ steps greedy's partial solution is at least as good as any rival's on some measure.

Worked example: where greedy breaks

Make 6 from coins worth 1, 3 and 4, in as few coins as possible. Greedy takes the largest that fits: 4, then 1, then 1 — three coins. The optimum is 3 + 3 — two coins. Taking the 4 destroyed the divisibility the 3s needed, and nothing warns you. The same greedy rule is optimal for coin systems like 1/5/10/25, which is why people assume it always works. The fix here is an $O(n \cdot \text{target})$ dynamic program.

Where it shows up

In interviews: interval scheduling and merging, jump game, gas station, task scheduler, Huffman coding, and the two classic greedy graph algorithms — Minimum Spanning Trees via Kruskal and Dijkstra's Shortest Paths. Expect the follow-up "prove it".

In trading systems: sweeping an order book to fill a size takes the cheapest price level first, which is provably optimal precisely because the book is already sorted by the right key. Smart order routers allocate across venues by expected cost per share, collateral desks deliver the cheapest eligible bond, and risk pipelines run the cheapest rejection test first. Each is a greedy rule resting on its ordering, and each breaks quietly the moment a fee, a rebate or a fill probability makes true cost non-monotonic in the sort key.