Greedy Algorithms: When They Work and When They Don't

A greedy algorithm makes the “best” local choice at each step and never reconsiders. When that local choice leads to a global optimum, greedy is simple and fast. When it doesn’t, you need something else (e.g. DP). This post explains when greedy works and gives classic examples.

What “greedy” means

• At each step: Choose the option that looks best right now (by some criterion: smallest, largest, earliest deadline, etc.).
• No backtracking: Once you choose, you don’t undo. So the algorithm is usually simple and efficient.
• Correctness: The tricky part is proving that this sequence of local choices actually gives a global optimum. For some problems it does; for others it doesn’t.

When greedy is correct

Greedy works when the problem has: