A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now and never reconsidering. When it works it is simple and fast; the catch, and the whole subtlety, is that it does not always work, so the real skill is recognizing when it is provably correct.
When greedy is correct
Two properties justify greed. The greedy-choice property says a globally optimal solution can be reached by making locally optimal choices, and optimal substructure says what remains after a greedy choice is a smaller instance of the same problem. The standard way to prove the greedy-choice property is an exchange argument: take any optimal solution, show you can swap one of its choices for the greedy choice without making it worse, and conclude a greedy solution is also optimal.
Interval scheduling, proved
To fit the most non-overlapping intervals, repeatedly take the one that finishes earliest among those still compatible. The exchange argument is short: the earliest-finishing interval leaves the most room for the rest, so any optimal schedule can have its first interval replaced by the earliest-finishing one without reducing the count. Sorting by finish time and sweeping once gives the optimum.
Classic greedy algorithms
Greedy is correct and standard in several famous places: Huffman coding builds an optimal prefix code by repeatedly merging the two least frequent symbols (Huffman 1952); Kruskal's and Prim's algorithms grow a minimum spanning tree by always adding the cheapest safe edge; Dijkstra greedily settles the nearest node; and fractional knapsack takes items by value-to-weight ratio.
When greedy fails
It is just as important to know the failures. The 0/1 knapsack is not greedy-solvable, because taking the highest ratio item can block a better combination, so it needs dynamic programming. Coin change with arbitrary denominations also breaks greedy (greedily using the largest coin can overshoot the optimum), which is why the DP version exists. Always confirm the exchange argument before trusting a greedy approach.
Step by step
- Find the right ordering or selection criterion (often a sort).
- Take the best available choice that keeps the solution valid.
- Never undo a choice.
- Justify it with an exchange argument: show swapping toward the greedy choice never hurts.
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1]) # earliest finish time first
count, end = 0, float('-inf')
for s, e in intervals:
if s >= end: # starts after the last kept one
count += 1
end = e
return count
Complexity (time and space)
Usually dominated by the sort, $O(n\log n)$, followed by a single linear pass, with $O(1)$ extra space. The asymptotics are rarely the hard part; the work is the correctness proof, since a greedy algorithm without an exchange argument is just a heuristic that may be wrong.
Worked example
Of four meetings, the most that can run without overlap is two:
print(max_non_overlapping([(1, 3), (2, 4), (3, 5), (0, 6)])) # 2
Follow-up questions
- What is the greedy-choice property? A globally optimal solution can be built by making locally optimal choices, which an exchange argument verifies.
- What is an exchange argument? Take an optimal solution and show you can swap one choice for the greedy one without worsening it, proving greedy is optimal.
- Why is 0/1 knapsack not greedy? Taking the best value-to-weight item can preclude a better whole-item combination; only fractional knapsack is greedy-solvable.
- Greedy vs DP? Greedy commits to one choice per step (fast, needs a proof); DP explores and caches subproblem answers when no safe greedy choice exists.
- Why sort interval scheduling by finish time? The earliest-finishing compatible interval leaves the most room for the rest, which the exchange argument shows is optimal.
References
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).
- Huffman, A Method for the Construction of Minimum-Redundancy Codes (1952).
- Skiena, The Algorithm Design Manual (3rd ed.).