A greedy algorithm makes the locally optimal choice at each step with the intent of finding a global optimum. Greedy algorithms work correctly when the problem has a greedy-choice property (a local optimum leads to a global optimum) and optimal substructure. Classic greedy problems include activity selection, fractional knapsack, Huffman coding, and minimum spanning trees. Correctness is typically proved via an exchange argument: showing that replacing a greedy choice with any alternative cannot improve the solution.
Implement activity selection (interval scheduling maximization) and Huffman encoding. For each problem, attempt a formal exchange argument for correctness before coding. Contrast greedy with DP: the 0/1 knapsack requires DP, while the fractional knapsack is solvable greedily.
A greedy algorithm builds a solution one step at a time, always making the choice that looks best right now without reconsidering past decisions. The appeal is efficiency: greedy algorithms are typically fast and simple to implement. The danger is incorrectness: making the locally optimal choice at each step does not automatically yield a globally optimal solution unless the problem has special structure.
The two properties that guarantee correctness are greedy-choice property and optimal substructure. Optimal substructure — which you've seen in dynamic programming — means that an optimal solution to the whole problem contains optimal solutions to its subproblems. The greedy-choice property is stronger: it says that a locally optimal (greedy) choice at each step is always part of *some* globally optimal solution. When both hold, you can safely commit to each greedy decision and recurse on what remains.
The canonical example is the activity selection problem: given a set of intervals (events with start and end times), select the maximum number of non-overlapping events. The greedy strategy — always pick the event that ends earliest — is provably optimal. Why? After choosing the earliest-ending event, the remaining problem is identical in structure, and no other first choice could leave more room for future events. This is the greedy-choice property in action. A formal proof uses an exchange argument: take any optimal schedule that doesn't start with the earliest-ending event; swap in the earliest-ending event instead; the result is no worse (it still fits, and the remaining time is at least as large).
Contrast this with the 0/1 knapsack problem, where items cannot be split. Greedy (take the highest value-per-weight item first) fails because committing to one item irrevocably forecloses combinations that would have been better. The fractional knapsack, where items can be broken into pieces, *does* have the greedy-choice property — you always take as much as possible of the highest ratio item — which is why it is solvable greedily while 0/1 requires dynamic programming. This contrast illustrates that the difference between greedy and DP is not about complexity but about problem structure.
In practice, many greedy algorithms require a sorted order or a priority queue to efficiently find the next best choice. Huffman coding builds an optimal prefix-free code by repeatedly merging the two lowest-frequency symbols — each merge requires finding the minimum, which is O(log n) with a min-heap, making the full algorithm O(n log n). Dijkstra's shortest-path algorithm is another greedy algorithm using a priority queue to always extend the currently shortest known path. Understanding greedy algorithms is therefore not just about knowing when they work, but about connecting the proof of correctness to the right data structure for implementation.