DSA · Greedy algorithms
Take the best move now, and never look back
Greedy commits to the locally best choice and never reconsiders. That is provably optimal for activity selection and fractional knapsack, and provably wrong for coin change with 1, 3 and 4. You will trace both, and learn the exchange argument that tells them apart.
Watch greedy lose to DP on 6 rupees →01 The idea
Commit to the best-looking step, and move on
A greedy algorithm builds an answer one choice at a time. At every point it takes whatever looks best right now by one fixed rule, adds it to the answer, and never reconsiders. No backtracking, no table of past results. That is why greedy code is short and fast: for most of the classics it is a sort followed by a single pass.
The catch is that "looks best right now" is a guess about the future. Sometimes the guess is provably safe — you can show that any optimal answer can be rewritten to begin with the greedy choice without getting worse. That rewriting is called an exchange argument, and it is the only thing separating a greedy algorithm from a hopeful one. When no exchange argument exists, greedy still runs, still returns something, and quietly returns the wrong thing.
02 Worked example
Five events, one hall, sorted by finish time
Five events want the same seminar hall: A 1–5, B 4–6, C 5–9, D 0–10, E 9–12. You may run any set that does not overlap, and you want as many events as possible. Sort by the time each event finishes — these five already are — then walk the list once, taking an event whenever it starts at or after the hall is free. Green boxes are taken, rose boxes are skipped forever.
Three events out of five, in one pass over the sorted list, with one number in memory. Everything rides on what the sort is keyed on. Finishing early is the only property that matters, because the event that frees the hall soonest leaves the most room for everything after it. How early an event starts and how long it runs are both irrelevant — and section 03 shows exactly what you lose by keying on those two instead.
03 The sorting key
Same loop, three keys, three different answers
The scan is three lines and never changes — lines 3 to 5 below. You hold one number, free, the time the hall is next available, and take an event when its start is at least that number. Only line 1 differs between these two versions. On the five events above, the left one returns 1 event and the right one returns 3.
Sorted by start time — wrong
sort events by start time ascendingfree = 0; taken = []for e in events: if e.start >= free: taken.add(e); free = e.endreturn takenSorted by finish time — correct
sort events by finish time ascendingfree = 0; taken = []for e in events: if e.start >= free: taken.add(e); free = e.endreturn taken| Sort key | Order it produces | Greedy takes | Result |
|---|---|---|---|
| Earliest finish | A B C D E | A, C, E | 3 events |
| Earliest start | D A B C E | D only | 1 event |
| Shortest duration | B E A C D | B, E | 2 events |
Why finish time is provably right. Let O be any optimal schedule and let f be the event that finishes earliest overall. If O does not start with f, swap its first event for f. Since f ends no later, nothing else in O can now clash, and the count is unchanged. So some optimal schedule starts with the greedy pick — and the same argument applies to whatever is left.
Why earliest start fails. Starting early says nothing about ending early. D starts at 0 and holds the hall until 10, which blocks all four of the other events — A, B and C all start before 10, and so does E. One greedy pick buys 1 event where finish time buys 3. The rule optimises a quantity that has no bearing on how much room is left afterwards.
Why shortest duration fails. A short event can sit exactly across the boundary between two longer ones. B runs 4–6, only two hours, and taking it kills both A (1–5) and C (5–9). Length is not what blocks other events; the finishing time is.
Cost. Sorting dominates at O(n log n); the pass itself is O(n) and holds one extra number, so it is O(1) beyond the taken list it returns. If the events already arrive sorted by finish time, the whole thing is one linear scan.
05 Where greedy fails
Coins 1, 3 and 4 — make exactly 6
Same shape of rule: at every step take the biggest coin that still fits. Greedy takes the 4 first, because 4 is the largest coin not bigger than 6. That leaves 2, and 2 can only be paid with two 1-coins. The answer is 4 + 1 + 1, three coins. The best answer is 3 + 3, two coins, and greedy can never reach it because it never considers passing up the 4.
Dynamic programming refuses to commit. It works out the cheapest way to make every amount from 1 up to 6, so by the time it reaches 6 it can compare "a 1 on top of the best answer for 5", "a 3 on top of the best answer for 3" and "a 4 on top of the best answer for 2", and keep the smallest.
Greedy — biggest coin first
sort coins descendingcount = 0while amount > 0: c = largest coin <= amount # none? give up amount = amount − c; count = count + 1return countDP — best answer for every amount
dp[0] = 0for a in 1..target: dp[a] = INF for c in coins: if c <= a: dp[a] = min(dp[a], dp[a − c] + 1)return dp[target]What greedy is actually assuming. Taking the 4 is a bet that some best answer for 6 contains a 4. It does not. That bet is safe only in a canonical coin system, where the largest-coin-first rule happens to be optimal at every amount. Indian 1, 2, 5, 10, 20, 50 and US 1, 5, 10, 25 are canonical, so greedy is safe on real money. 1, 3, 4 is not, and nothing in the code notices.
What DP does differently. It never commits, so it pays for that with a table. Cost is O(target × number of coins) time and O(target) space, against greedy's O(n log n) sort plus a handful of subtractions. On amount 6 with three coins the inner loop runs 6 × 3 = 18 times, against greedy's 3 coin picks — and DP is the only one of the two that is correct.
Greedy can also get stuck. Drop the 1-coin and use only 3 and 4. Greedy takes the 4, is left with 2, finds no coin that small, and reports that 6 cannot be paid. 3 + 3 pays it exactly. A wrong answer is bad; a confident "impossible" is worse.
06 Cheat sheet
Which greedy rules are actually proved
| Problem | Greedy key | Verdict |
|---|---|---|
| Activity selection | earliest finish time | O(n log n) correct · exchange argument |
| Fractional knapsack | highest value ÷ weight | O(n log n) correct · the last item can be cut |
| 0/1 knapsack | highest value ÷ weight | wrong · needs DP, O(nW) |
| Coin change, canonical coins (1 2 5 10) | largest coin that fits | O(n log n) correct · true for real currency |
| Coin change, arbitrary coins (1 3 4) | largest coin that fits | wrong · needs DP, O(target × n) |
| Huffman coding | merge the two smallest frequencies | O(n log n) correct · with a min-heap |
| Minimum spanning tree (Kruskal) | cheapest edge joining two components | O(E log E) correct · cut property |
| Shortest path with a negative edge | settle the nearest node (Dijkstra) | wrong · needs Bellman–Ford, O(VE) |
07 Where & why
When to reach for greedy, and what to reach for instead
Greedy is the cheapest correct algorithm when it is correct — a sort and one pass, O(n log n), against DP's table at O(n × W) time and memory. The entire decision is whether you can defend the choice rule, and in an interview you will be asked to defend it out loud.
Reach for it when…
Use something else when…
| Situation | Better choice | Why |
|---|---|---|
| Taking one item changes what the remaining items are worth | Dynamic programming | DP keeps every sub-answer instead of committing. 0/1 knapsack is exactly this shape, at O(nW). |
| Coin denominations you do not control | DP over amounts | Greedy is only correct on canonical systems. 1, 3, 4 on amount 6 already breaks it, and 3, 4 makes it give up entirely. |
| You need every optimal answer, or a count of them | DP or backtracking | Greedy walks one path and cannot enumerate the others, because it has thrown them away. |
| Edge weights can be negative | Bellman–Ford | Dijkstra settles the nearest node and never revisits it; a negative edge can make a settled distance shrink later. |
08 Interview questions
What interviewers actually ask
Ten questions in the order an interview escalates: what greedy is, why finish time works, the coin-change counterexample that decides the round, and then how you tell the two apart on a problem you have never seen.
What does it mean for an algorithm to be greedy?
Why does sorting by finish time work for activity selection?
Give a case where a greedy choice is provably wrong.
When IS greedy coin change correct?
How do you decide whether greedy applies to a new problem?
What is the exchange argument?
What is the complexity of activity selection?
Greedy versus dynamic programming — how do you choose?
Is fractional knapsack greedy, and is 0/1 knapsack?
Why is sorting by shortest duration a tempting but wrong key?
09 Practice problems
Six problems, in order of bite
Every one is solvable with what is above: a sort followed by one committed pass, the exchange argument that says whether that pass is safe, and the DP you fall back on when it is not.