juniorGreedy Algorithms

When does a greedy algorithm produce an optimal solution?

Updated Feb 20, 2026

Short answer

A greedy algorithm is provably optimal when the problem has two properties: the greedy-choice property, meaning a locally optimal choice is part of some globally optimal solution, and optimal substructure, meaning an optimal solution contains optimal solutions to its subproblems. Without both, greedy still runs fast but can return an arbitrarily poor answer — and it never backtracks to find out.

Deep explanation

Greedy makes the best-looking choice at each step and never reconsiders. That is why it is fast, and why it is often wrong.

The two properties, concretely.

Greedy-choice property — you can prove that taking the locally best option never rules out an optimal solution. The standard proof is an exchange argument: assume an optimal solution that does not contain your greedy choice, then show you can swap the greedy choice in without making the solution worse.

Optimal substructure — after making that choice, the remaining problem is a smaller instance of the same problem, and solving it optimally yields an overall optimum.

Where greedy provably works: interval scheduling by earliest finish time, Huffman coding, Dijkstra with non-negative weights, Kruskal and Prim for minimum spanning trees, the fractional knapsack.

Where it fails, and why the failure is instructive:

TypeScript
0/1 knapsack, capacity 10:
  A: value 60, weight 10   -> ratio 6.0
  B: value 50, weight 5    -> ratio 10.0
  C: value 50, weight 5    -> ratio 10.0


Greedy by value/weight: take B, then C  -> value 100, weight 10.  Optimal here.


Now capacity 6:
  A: value 60, weight 6    -> ratio 10.0
  B: value 50, weight 5    -> ratio 10.0
Greedy takes A or B by tie-break; picking B leaves 1 unit unusable -> 50, not 60.

The fractional version is greedy-optimal, because you can always fill the remaining capacity with a fraction of the next item — the greedy-choice property holds. Making items indivisible destroys it, and 0/1 knapsack requires dynamic programming.

Coin change is the other classic: greedy works for {1, 5, 10, 25} but for {1, 3, 4} and target 6 it takes 4+1+1 = three coins when 3+3 = two is optimal.

The practical discipline: never assume greedy works because it produces good answers on your test cases. Either prove the exchange argument, or find a counterexample. If you can do neither quickly, dynamic programming is the safe fallback — slower, but correct.

Real-world example

Interval scheduling — greedy is optimal, but only with the right criterion:

Python
def max_meetings(intervals):
    intervals.sort(key=lambda x: x[1])       # by EARLIEST FINISH time
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Sorting by earliest finish is provably optimal: the meeting that finishes first leaves the most room for everything else, and an exchange argument shows swapping it into any optimal schedule never hurts.

Sorting by earliest start or shortest duration both seem reasonable and both fail. Shortest duration: intervals (1,10), (9,11), (10,20) — greedy takes the short (9,11) and blocks both others, scheduling one meeting where two were possible.

Common mistakes

  • - Assuming greedy is correct because it passes the examples, without an exchange-argument proof or a search for counterexamples.
  • - Applying greedy to 0/1 knapsack
  • only the fractional version has the greedy-choice property.
  • - Assuming greedy coin change works for arbitrary denominations — it holds for common currencies by construction, not in general.
  • - Choosing a plausible-sounding greedy criterion without testing alternatives
  • for interval scheduling, earliest-finish works while shortest-duration does not.
  • - Using Dijkstra on graphs with negative edge weights, where the greedy choice property fails and Bellman-Ford is required.
  • - Forgetting that greedy never backtracks, so a single wrong early choice cannot be recovered later.

Follow-up questions

  • What is an exchange argument?
  • Why does Dijkstra's algorithm fail on negative edges?
  • How do greedy and dynamic programming relate?
  • Is greedy ever useful when it isn't optimal?

More Greedy Algorithms interview questions

View all →