The Core Idea
A greedy algorithm makes the locally optimal choice at each step and never revisits it. There is no backtracking, no exploration of alternatives — just 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.
Watch the visualizer execute the algorithm on a set of overlapping intervals — notice how sorting by finish time drives every decision:
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.
See the ratio-based selection in action:
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.
Try the scheduler on a mixed set of deadlines and profits:
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.
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²) |
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²).
Key Takeaways
- 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.