Pattern 15 of 18 · Final Stretch

Greedy

Make the locally optimal choice at each step and prove it leads to a global optimum.

Make the choice that looks best right now, without reconsidering it later, and trust that a sequence of locally optimal choices adds up to a globally optimal answer. It only works when the problem actually has that property.

Key concepts

  • Local optimality: at each step, pick the option that's best by some clear criterion (soonest deadline, largest value, smallest cost).
  • No backtracking: once a greedy choice is made, it's never revisited — that's what keeps greedy algorithms fast, often O(n log n) after a sort.
  • Exchange argument: the usual way to justify a greedy choice — show that swapping it for any other choice can't make the answer better.

When to use it

  • Sorting the input by some key, then making one pass with simple local decisions, intuitively seems to produce the best answer.
  • The problem involves intervals, scheduling, or resource allocation where "always take the best available option" tends to work.

Tips

  • Before trusting a greedy idea, try to find a counterexample — if you genuinely can't, that's a good sign.
  • Sorting first (by start time, end time, or value) is almost always the first step in a greedy solution.
  • If greedy doesn't work, that's usually a strong hint the problem is actually dynamic programming.

Practice problems (8)

Blind 75 (2):

More from Blind 150 (6):

← 2-D Dynamic ProgrammingIntervals →

See the full roadmap →