Skip to main content

🎯 Greedy

Greedy is "take the best local choice and hope it stays optimal". When it works it is the simplest solution; when it does not, you need DP. Always prove it works — counterexample first.

This category contains 9 problems. Use the patterns below to recognize what's being asked, then jump to the problem list at the bottom.

🧠 Key Patterns​

  • Interval Scheduling — Sort by end time, take earliest-finishing.
  • Activity Selection — Maximize non-overlapping count.
  • Jump Game — Track furthest reachable index as you scan.
  • Huffman-like — Repeatedly merge two smallest (heap).
  • Exchange Argument Proofs — Show swapping any pair never improves the greedy choice.

⚠️ Common Pitfalls​

  • Assuming greedy works without proof — many problems look greedy but need DP (coin change with arbitrary denominations).
  • Sorting key matters: by start vs by end can give very different results.

📚 Study Resources​

📺 Videos​

📖 Books​

  • Algorithm Design — Kleinberg & Tardos — Ch. 4 — best treatment of greedy proofs anywhere
  • Introduction to Algorithms (CLRS) — Ch. 16

🌐 Articles & References​

💻 All Greedy Problems​

Last updated on