What Makes an Algorithm "Greedy"
A Greedy Algorithm builds up a solution piece by piece, always choosing the option that looks best at the current moment, without ever reconsidering that choice later. This is a much simpler and typically faster strategy than dynamic programming, discussed earlier in this series, which systematically explores all subproblem combinations. The catch is that greedy choices are not always globally optimal — but for a specific class of problems, they provably are, and recognizing this class is the central skill this article develops.
The Activity-Selection Problem
Given a set of n activities, each with a start time sᵢ and finish time fᵢ, the goal is to select the maximum-size subset of mutually compatible activities — activities whose time intervals do not overlap — that can all be scheduled using a single resource, such as one lecture hall.
Example activities (sorted by finish time):
i: 1 2 3 4 5 6 7 8 9 10 11
sᵢ: 1 3 0 5 3 5 6 8 8 2 12
fᵢ: 4 5 6 7 8 9 10 11 12 13 14The Naive Dynamic Programming Approach
This problem does have optimal substructure, discussed earlier in this series, and could be solved with dynamic programming: define S_{ij} as the set of activities that start after activity i finishes and finish before activity j starts, and recursively consider every possible activity k in that set as a potential inclusion, similar in spirit to the matrix-chain and optimal-BST recurrences covered earlier in this series. This approach works, but at a cost of Θ(n³) time — more work than necessary, as the next section reveals.
The Greedy Insight: Always Pick the Earliest Finish Time
The key insight that unlocks a far simpler and faster solution is this: among all activities, the one that finishes earliest should always be included in some optimal solution. Intuitively, choosing the activity that finishes soonest leaves the maximum possible remaining time for scheduling additional activities afterward.
GREEDY-ACTIVITY-SELECTOR(s, f, n):
sort activities by finish time f (ascending)
A = {activity 1} // the first activity to finish
k = 1
for m = 2 to n:
if s[m] ≥ f[k]: // this activity starts after the last selected one finishes
A = A ∪ {activity m}
k = m
return AApplying this to the example above: sort by finish time (already sorted), select activity 1 (finishes at 4), then scan forward for the next activity whose start time is at least 4 — activity 4 (starts at 5, finishes at 7) qualifies, then activity 8 (starts at 8, finishes at 11), then activity 11 (starts at 12, finishes at 14). This produces a selection of 4 activities, which can be verified to be optimal.
Since the activities only need to be sorted once, taking Θ(n log n) time, followed by a single linear pass through the sorted list, the total running time is Θ(n log n) — a dramatic improvement over the Θ(n³) dynamic programming approach.
Why the Greedy Choice Is Provably Correct Here
The correctness of this greedy strategy rests on proving two properties, which together justify replacing the full dynamic programming exploration with a single greedy pass.
The Greedy-Choice Property
A problem exhibits the Greedy-Choice Property if a globally optimal solution can always be reached by making a locally optimal (greedy) choice first, without needing to explore other options at that step. For activity selection, this is proven by an "exchange argument": given any optimal solution, if it does not already include the activity with the earliest finish time, that activity can always be swapped in to replace whatever activity currently occupies the first slot, without reducing the total number of activities selected, since the earliest-finishing activity leaves at least as much room for subsequent choices.
Optimal Substructure (Revisited)
As with dynamic programming, discussed earlier in this series, an optimal solution to the overall problem must contain optimal solutions to its subproblems. Once the greedy choice is made, the remaining problem — selecting the maximum compatible set from the activities that start after the chosen activity finishes — is a smaller instance of exactly the same problem, and it must itself be solved optimally for the overall solution to be optimal.
Together, these two properties justify a much simpler algorithmic structure than dynamic programming: rather than solving every subproblem and combining results, a greedy algorithm makes one choice, then recursively (or iteratively) solves the single remaining subproblem, without ever needing to reconsider or backtrack on the initial choice.
Huffman Coding: A Greedy Algorithm for Optimal Compression
Huffman Coding solves the problem of encoding a set of characters into binary strings such that the total encoded length of a document is minimized, given the frequency of each character. Its key idea is a Variable-Length Prefix Code: characters that appear more frequently get shorter binary codes, and no code is a prefix of another, allowing unambiguous decoding without any separator between characters.
Example character frequencies:
a: 45 b: 13 c: 12 d: 16 e: 9 f: 5
A fixed-length code would need 3 bits per character
(since there are 6 characters), for a total of:
45·3 + 13·3 + 12·3 + 16·3 + 9·3 + 5·3 = 300 bits
An optimal Huffman code produces:
a: 0 (1 bit)
b: 101 (3 bits)
c: 100 (3 bits)
d: 111 (3 bits)
e: 1101 (4 bits)
f: 1100 (4 bits)
Total: 45·1 + 13·3 + 12·3 + 16·3 + 9·4 + 5·4 = 224 bitsThis represents a significant reduction, roughly 25% smaller, achieved simply by assigning shorter codes to the more frequent characters.
Building the Huffman Tree Greedily
The algorithm builds an optimal prefix code by repeatedly combining the two least-frequent remaining items into a new combined node, using a min-priority queue, discussed earlier in this series regarding heaps, to always efficiently retrieve the two smallest frequencies.
HUFFMAN(C, n):
build a min-priority queue Q from the characters in C
for i = 1 to n - 1:
allocate a new node z
z.left = x = EXTRACT-MIN(Q)
z.right = y = EXTRACT-MIN(Q)
z.freq = x.freq + y.freq
INSERT(Q, z)
return EXTRACT-MIN(Q) // the root of the Huffman treeAt each step, the greedy choice is to merge the two currently lowest-frequency nodes, since this minimizes the increase in total encoded length caused by giving both merged items one additional bit in their eventual code. This greedy choice can be proven optimal using an exchange argument similar in structure to the one used for activity selection: any optimal tree can be rearranged so that the two lowest-frequency characters are siblings at the deepest level, without increasing the total cost.
Using a min-heap for the priority queue, each of the n-1 iterations performs two EXTRACT-MIN operations and one INSERT, each costing O(log n), giving a total running time of O(n log n).
Why Greedy Algorithms Are Valuable When They Apply
Both examples in this article achieve dramatically better running times than a full dynamic programming approach would require — Θ(n log n) instead of Θ(n³) for activity selection — precisely because the greedy-choice property eliminates the need to explore multiple options at each decision point. This is the central trade-off in algorithm design: greedy algorithms are simpler and faster than dynamic programming whenever the greedy-choice property can be proven, but applying a greedy strategy to a problem that lacks this property, without first proving it holds, can silently produce an incorrect, suboptimal result. The exchange-argument proof technique demonstrated in this article for both activity selection and Huffman coding is the standard tool for establishing that a greedy strategy is actually correct before trusting it.