Basic Greedy
Quick reference
| Activity selection | O(n log n) |
| Two-pointer greedy matching | O(n log n) |
| Reachability scan | O(n) |
| Exhaustively trying every choice (the alternative to greedy) | O(2^n) typical |
A greedy algorithm makes the best-looking choice available right now, locks it in, and never looks back to reconsider it. There is no backtracking, and no "what if I had chosen differently three steps ago". Given what is in front of you this instant, take the best option and continue.
Think about how to make change with the fewest coins, with US denominations: pennies, nickels, dimes, quarters. The greedy way: always take the biggest coin that still fits under the remaining amount. You owe 41 cents? Take a quarter (16 left), then a dime (6 left), then a nickel (1 left), then a penny. Four coins, and it is the fewest possible. For US coins, to always take the biggest coin that fits produces the optimal answer. But this is a fact about these specific denominations, not a law of the universe. The real skill in greedy algorithms was never "take the biggest thing first". It is to know when that instinct is actually safe to trust for the problem in front of you, and when it is not. Break It below shows exactly where this coin analogy stops working.
The shape of a greedy algorithm
# Greedy is not a data structure. It is a strategy applied to plain arrays, # usually after a sort that makes "locally best" well-defined: # # sort the input by whatever makes the next choice comparable # walk through one time, left to right # at each step, take the option that looks best right now # never revisit or undo a choice already made # # Three classic shapes it takes, below: pick non-overlapping intervals, # match two sorted lists against each other, and track one running value # during a single scan.
interval / activity selection — sort by end time, take what still fits
function activitySelection(activities): // each activity is (start, end)
sort activities by end ascending
chosen = []
lastEnd = -infinity
for (start, end) in activities:
if start >= lastEnd: // does not overlap the last one taken
chosen.append((start, end))
lastEnd = end
return chosentwo-pointer greedy matching — smallest available resource to smallest need that still fits
function matchSmallestFit(needs, resources):
sort needs ascending
sort resources ascending
i = 0 // pointer into needs
j = 0 // pointer into resources
matched = 0
while i < needs.length and j < resources.length:
if resources[j] >= needs[i]: // this resource is big enough to cover this need
matched += 1
i += 1 // this need is satisfied: move to the next need
j += 1 // this resource is spent either way: move to the next one
return matchedreachability tracking — furthest index reachable so far, one scan
function canReachEnd(jumps):
furthest = 0
for i from 0 to jumps.length - 1:
if i > furthest: // cannot even get to i, and not past it
return false
furthest = max(furthest, i + jumps[i])
return furthest >= jumps.length - 1Every example above is dominated by its sort, if it needs one: O(n log n) time, with the linear scan after it disappearing into that bound. The reachability scan needs no sort at all, so it is O(n). The extra space is O(1) to O(n), usually only a few running variables, sometimes an output list. The whole appeal is what greedy avoids. To try every possible combination of choices is often exponential. Greedy replaces that with a single pass, but only for problems where the greedy choice is actually provably safe. That is a property of the problem, not something that you get for free by a greedy choice.
| Operation | Time | Space | Why |
|---|---|---|---|
| Activity selection | O(n log n) | O(1) extra | The sort by end time dominates. The scan after it touches each activity one time. |
| Two-pointer greedy matching | O(n log n) | O(1) extra | The sort of both sides dominates. The two pointers then each walk their list one time, together. |
| Reachability scan | O(n) | O(1) | No sort is needed. The state is a single running maximum, updated one time per index. |
| Exhaustively trying every choice (the alternative to greedy) | O(2^n) typical | O(n) (recursion) | Without a proof that the greedy choice is safe, the honest fallback is to try every combination. This is exactly the cost that greedy tries to avoid, and exactly why greedy is only worth using once you can justify it. |
The classic counterexample — greedy is not always optimal
Greedy takes the biggest coin that fits, every time: 4, then 1, then 1, which is three coins. But 3 + 3 is two coins, strictly better, and greedy never finds it, because after it takes the 4 it never reconsiders. This is the whole lesson from The Idea, made concrete. The coin analogy works for US currency and breaks here, on denominations that look just as reasonable. Greedy needs a proof that it is safe for the specific problem, not a feeling that it probably is.
Forgetting to sort first
The safety argument of activity selection depends completely on a visit to the soonest-ending activity first. If you feed it activities in random input order, the same "take it if it does not overlap" logic produces a smaller, wrong answer, because it commits to a bad early choice before it ever sees the good one.
Committing to the greedy choice without checking why it's safe
Every working example above has an actual argument for why the locally-best choice cannot cost you the globally-best answer. Build It states each one. To skip that check and only trust the greedy instinct is how you end up with a fast, confident, wrong answer. It passes on the first three test cases that you try and fails on the fourth.
Off-by-one on interval boundaries
If one activity ends exactly when the next one starts, do they overlap or not? start >= lastEnd treats a shared boundary point as fine (back-to-back, no overlap). start > lastEnd would reject it. Both are defensible. But the problem statement picks one, and the wrong comparison quietly drops or admits one extra interval at every boundary case, with no error.
Sign in to mark problems done — progress syncs across devices.