Intuition First: Making Change at the Till#
When a cashier hands you change, they don't search every possible combination of coins. They just grab the largest coin that still fits, then the next largest, and so on. Want to give ₹87? Reach for the ₹50, then ₹20, then ₹10, then ₹5, then ₹2. Each grab is the best-looking move right now, with no second-guessing. For standard coin systems, that simple instinct happens to give the fewest coins every time.
That's a greedy algorithm: take the locally best option and never look back. The catch, and the whole tension of this topic, is that the instinct is only sometimes right. Part of learning greedy is learning to spot when "grab the best now" provably wins, and when it quietly leads you astray.
The Core Idea#
A greedy algorithm makes the locally optimal choice at each step and never revisits it. There is no backtracking and no exploring alternatives: you pick the best-looking option right now and move on.
That sounds reckless, but for a surprising number of problems it is provably correct. The two conditions that guarantee correctness are:
- Greedy-choice property: a globally optimal solution can always be assembled from locally optimal choices. You can make the greedy selection first, then solve the remaining subproblem, and the combined solution is globally optimal.
- Optimal substructure: as with dynamic programming, the optimal solution to a problem contains optimal solutions to its subproblems.
Both conditions sound similar to DP's requirements. The key difference is the greedy-choice property: DP considers every possible choice and combines sub-results; greedy commits to one choice before solving any subproblem. When the greedy-choice property holds, that single commitment is always safe.
Activity Selection: Sort by Finish Time#
Problem: Given n activities, each with a start and finish time, choose the largest non-overlapping subset.
Greedy rule: Always pick the activity that finishes earliest. After choosing it, discard every activity that conflicts, then repeat.
Why it works: An activity that finishes early leaves the most room for future activities. Formally, suppose an optimal solution starts with activity x instead of the earliest-finishing activity e. You can swap x for e without reducing the count because e ends no later than x, so nothing it conflicts with will conflict with e less.
Let's take the example in this visualization: eight activities, A through H, drawn as bars on a shared timeline: A (1-4), B (3-5), C (0-6), D (5-7), E (3-9), F (5-9), G (6-10) and H (8-11). They are already sorted by finish time, which is the entire preprocessing step.
Press play and follow the lastFinish marker. A is taken first because it finishes soonest; B and C are then rejected on sight because they start before 4. D (5-7) clears the marker and is taken, knocking out E, F and G, and H (8-11) closes the run. Three activities selected. Notice that C, the longest bar (spanning 0 to 6), is rejected despite starting earliest: a greedy rule keyed on start time or on duration would have picked differently and done worse.
Fractional Knapsack: Sort by Value/Weight Ratio#
Problem: Given items each with a weight and value, fill a capacity-W knapsack to maximize total value. Unlike the 0/1 variant, items can be split.
Greedy rule: Sort items by value-per-unit-weight (descending). Take each item fully until the knapsack is full; if the last item does not fit entirely, take the fractional part that fills the remaining capacity.
Why it works (and why 0/1 is different): Because items are divisible, you can always act on the best ratio without worrying about wasted capacity: any leftover space is filled with the next-best-ratio item. With indivisible items this reasoning breaks: taking the highest-ratio item might leave a gap that a slightly worse ratio would have filled better with the space it freed. That is exactly why 0/1 knapsack requires DP rather than a greedy pass.
Let's take the example in this visualization: a knapsack that holds 5 and four items: (weight 2, value 10), (4, 16), (6, 12) and (3, 3).
Press play and watch the ratio column decide everything. The ratios are 5, 4, 2 and 1, so the first item goes in whole, using 2 of the 5 units and leaving 3. The second item weighs 4 and no longer fits, so it is split: three quarters of it enter the pack for three quarters of its value, 12. Total 22, and the knapsack is exactly full. That final partial item is the step the 0/1 version cannot take, and the reason it needs a DP table instead.
Job Sequencing: Maximize Profit with Deadlines#
Problem: Each job has a profit and a deadline (the latest time-slot by which it must complete). Each job takes exactly one time unit. Schedule jobs to maximize total profit.
Greedy rule: Sort jobs by profit descending. For each job, try to schedule it in the latest available slot before its deadline. If such a slot exists, take it; otherwise skip the job.
Why it works: Scheduling in the latest free slot preserves earlier slots for future (potentially more profitable) jobs. The greedy profit-first ordering ensures higher-profit jobs are never displaced by lower-profit ones.
Let's take the example in this visualization: three one-unit time slots and five jobs: J1 (deadline 2, profit 100), J2 (1, 19), J3 (2, 27), J4 (1, 25) and J5 (3, 15).
Press play and watch the slot row rather than the job list. J1 is richest, so it goes first and takes slot 2, not slot 1, because 2 is the latest slot its deadline allows. That choice is what saves slot 1 for J3, which lands there next. J4 and J2 then both want slot 1, find it occupied, and are dropped outright; J5 takes slot 3. Total profit is 142 out of a possible 186. Two jobs simply cannot be scheduled, and the greedy profit-first order guarantees the two that are dropped are the cheapest ones that had to go.
Coin Change#
Greedy coin change always takes the largest coin that fits. This is optimal for canonical coin systems (like US coins) but can fail for arbitrary denominations, which is exactly why the dynamic-programming version exists.
Let's take the example in this visualization: the US denominations [25, 10, 5, 1] and a target of 36. Press play and watch the remainder shrink: 36 → 11 after one quarter, → 1 after one dime, → 0 after one penny. Three coins, and for this coin system that is provably optimal. Swap in a non-canonical set such as [1, 3, 4] and the same rule stops being optimal. The Coin Change article works through the DP table that fixes it.
Code Implementation#
Complexity Analysis#
| Problem | Sort | Greedy pass | Total |
|---|---|---|---|
| Activity selection | O(n log n) | O(n) | O(n log n) |
| Fractional knapsack | O(n log n) | O(n) | O(n log n) |
| Job sequencing | O(n log n) | O(n²) worst | O(n²) |
| Greedy coin change | O(n log n) | O(n) | O(n log n) |
The bottleneck is always the sort for activity selection and fractional knapsack. Job sequencing's inner loop (finding the latest free slot) can be improved to O(n log n) with a disjoint-set structure, but the naive version is O(n²).
What to Remember#
- Greedy is not always correct. The algorithm must satisfy both the greedy-choice property and optimal substructure. Without a proof, greedy is just a heuristic.
- Contrast with DP. DP explores all choices and stores sub-results; greedy commits early. Greedy is faster, but only safe when the structure allows it.
- The fractional/0-1 knapsack split is the canonical example: divisibility changes which paradigm applies.
- Activity selection is the textbook greedy proof. The exchange argument (swap the optimal choice for the greedy one without loss) is worth understanding before tackling more complex problems.