Greedy Algorithms Explained: Choices That Need Proof

By Hourly DSA · September 30, 2026 · 4 min read

A greedy algorithm commits to a local choice and continues without reconsidering it. The challenge is proving that the choice still allows a globally optimal answer. A rule that feels sensible can fail on a small input.

Start with the exact objective. Maximizing the number of meetings, maximizing their total value, and merging their occupied time are different tasks, even when all three use intervals.

A greedy rule that works: finish meetings early

Suppose you want to attend as many nonoverlapping meetings as possible. Each meeting has a start and an end, lasts a positive amount of time, and counts equally. You may attend a meeting that starts exactly when another ends.

Consider:

A: [0, 7)
B: [1, 3)
C: [3, 5)
D: [5, 7)

Choosing the earliest-starting meeting selects A and blocks everything else. You attend one meeting.

Choosing the compatible meeting that finishes earliest selects B, then C, then D. You attend three.

The algorithm sorts by end time and scans once. Accept a meeting when its start is at least the end of the last accepted meeting. If none has been accepted yet, accept the first one.

Sorting takes O(n log n) time with a comparison sort, and the scan takes O(n). The [start, end) notation excludes the end instant, so back-to-back meetings are compatible.

Why earliest finish is safe

Let G be a meeting with the earliest finishing time. Take any optimal schedule and look at its first meeting, X.

If X is already G, there is nothing to change. Otherwise, replace X with G. G finishes no later than X, so every meeting that could follow X can still follow G. The number of meetings stays the same.

Therefore, at least one optimal schedule begins with the greedy choice. After choosing G, apply the same reasoning to the compatible meetings that remain.

This is an exchange argument: show that an optimal answer can adopt your choice without becoming worse. Antti Laaksonen's Competitive Programmer's Handbook, chapter 6 discusses greedy correctness and scheduling examples.

Why shortest duration is a different rule

Now consider these meetings:

A: [0, 4)
B: [3, 5)
C: [4, 8)

B is shortest, lasting two units. But it overlaps both A and C. Selecting B first leaves only one meeting, while selecting A and C gives two.

“Leave more time available” sounds plausible, but duration alone ignores where that time sits. Earliest finish has a specific exchange argument. Shortest duration does not inherit that proof.

When explaining an algorithm, name the actual sorting key. “Sort the meetings and use greedy” leaves the most important decision unspecified.

Coin change exposes another tempting rule

Suppose unlimited coins have values 1, 5, and 7, and you want to make 10 with the fewest coins.

A largest-coin-first rule takes 7, then three 1s. That uses four coins. Choosing 5 and 5 uses only two, which is optimal because no single coin has value 10.

The first local choice looked attractive because it removed the most remaining value. It also left an expensive remainder.

This counterexample disproves that rule for arbitrary denominations. It does not mean every coin system defeats greedy; it means the denomination set needs a justification before you rely on that strategy.

A dynamic programming formulation can compare possible final coins for each amount. Our guide to defining a DP state explains how to build that kind of recurrence from the answer's meaning.

Changing the objective can break the proof

Return to meetings, but give each one a value:

Meeting	Interval	Value
A	[0, 3)	5
B	[3, 6)	5
C	[0, 6)	20

Earliest finish selects A and B for a total value of 10. Selecting C alone gives 20.

The earlier exchange argument preserved the number of meetings, not their total value. Replacing a valuable meeting with an earlier-finishing one can reduce the objective, so that proof no longer applies.

Likewise, if the task asks for the union of occupied time, use merge intervals. There is no need to choose a subset of compatible meetings at all.

How to evaluate a greedy idea

Write down the local choice precisely, then ask what an optimal answer loses if it adopts that choice. Try a small input where the attractive option blocks two useful alternatives, or where the leftover work becomes unusually costly.

Passing a few examples can increase your understanding, but it is not a proof. A single counterexample, however, is enough to reject a universal correctness claim.

For a short practice question, ask: “Why can the first meeting in an optimal schedule be replaced by the earliest-finishing meeting?” The answer should mention that all later meetings remain compatible and the count is preserved.

Use Hourly DSA for focused reasoning practice, then record any failed assumption using the DSA mistake-review method. A useful note names the choice, the counterexample, and the condition a correct proof would need.