Greedy algorithms

Greedy algorithms make the locally best choice and never revisit it. They are attractive because implementation is often small, but correctness requires proof: an exchange argument, a staying-ahead invariant, or a matroid-like property that makes local choices safe.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Expect interval scheduling, coin-like choices, jump games, and sorting by a key before making one pass. Explain why the chosen order is not arbitrary.

Common pitfalls: A greedy-looking solution can fail when an early choice blocks a better future. Provide a counterexample search before committing, especially for knapsack-like problems.

Checklist:

• State local choice.
• Prove exchange or invariant.
• Sort by the right key.
• Check counterexamples.