Greedy Algorithms: How to Know Greedy Works

📅 2026-11-09T19:08:42.077Z
👁️ 35 katselukertaa
🔓 Julkinen


# Greedy Algorithms: How to Know Greedy Works

Greedy algorithms make the locally best choice at each step. They are fast and elegant, but only correct for problems with the right structure.

**Signs greedy may work.**
- Sorting by one attribute seems to make the decision obvious.
- Making the best choice now never blocks a better choice later.
- The problem resembles a known greedy problem: interval scheduling, jump game, gas station, assign cookies.

**Proving it (briefly).** Interviewers don't want a formal proof, but they do want a reason. Two common arguments:
- *Exchange argument:* any optimal solution can swap its choice for the greedy one without getting worse.
- *Stays ahead:* after each step, the greedy solution is at least as good as any other.

**Examples.**
- *Jump game:* track the farthest reachable index; if you ever pass it, return false.
- *Gas station:* if the total gas is at least the total cost, the answer starts right after the point where the running tank last went negative.
- *Minimum arrows to burst balloons:* sort by end, shoot at the earliest end.

**When greedy fails.** Coin change with arbitrary denominations is the classic counterexample; it needs dynamic programming. Mentioning a counterexample shows real understanding.

Practice saying the one-line reason for each greedy choice. Running problems with an [live interview coaching](https://www.ai-interviewcopilot.com/) helps you get used to justifying it.

*Written by the AI Interview Copilot team.*