/Interview Study Guide/Algorithms & data structures
Concepts

Greedy

Algorithms

Take the locally-best choice each step — fast and simple, but only correct when you can prove it.

Definition

A greedy algorithm makes the locally-optimal choice at each step and never reconsiders. It's fast and simple, but only correct when the problem has the greedy-choice property and optimal substructure — which must be argued (often via an exchange argument), not assumed.

When to use

Reach for greedy on interval scheduling, jump games, and Huffman-style problems — usually after sorting. When a greedy choice provably leads to a dead end, the fallback is dynamic programming, which considers all choices.