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. No backtracking, no "what if I'd chosen differently three steps ago" — just: given what's in front of you this instant, take the best option and move on.
Think about making change with the fewest coins, using US denominations — pennies, nickels, dimes, quarters. The greedy way: always grab the biggest coin that still fits under the remaining amount. 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 happens to be the fewest possible. For US coins, always taking the biggest coin that fits happens to always produce the optimal answer — but that's a fact about these specific denominations, not a law of the universe. The real skill in greedy algorithms was never "grab the biggest thing first" — it's knowing when that instinct is actually safe to trust for the problem in front of you, and when it isn't. Break It below shows exactly where this coin analogy stops working.
The shape of a greedy algorithm
# greedy isn't a data structure — it's 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 once, 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 this takes, below: picking non-overlapping intervals, # matching two sorted lists against each other, and tracking one running value # while scanning once.
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: // doesn't 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: // can't even get to i, let alone 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's O(n). Extra space is O(1) to O(n) — usually just a few running variables, occasionally an output list. The entire appeal is what greedy avoids: trying every possible combination of choices is often exponential, and greedy replaces that with a single pass — but only for problems where the greedy choice is actually provably safe, which is a property of the problem, not something you get for free by choosing greedily.
| Operation | Time | Space | Why |
|---|---|---|---|
| Activity selection | O(n log n) | O(1) extra | Sorting by end time dominates; the scan afterward touches each activity once. |
| Two-pointer greedy matching | O(n log n) | O(1) extra | Sorting both sides dominates; the two pointers then each walk their list once, together. |
| Reachability scan | O(n) | O(1) | No sort needed — the state is a single running maximum updated once 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 trying every combination — which is exactly the cost greedy is trying to avoid, and exactly why greedy is only worth reaching for once you can justify it. |
The classic counterexample — greedy is not always optimal
Greedy grabs the biggest coin that fits, every time: 4, then 1, then 1 — three coins. But 3 + 3 is two coins, strictly better, and greedy never finds it because after taking 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 are just as reasonable-looking. Greedy needs a proof it's safe for the specific problem, not a vibe that it probably is.
Forgetting to sort first
Activity selection's safety argument depends entirely on visiting the soonest-ending activity first — feed it activities in random input order and the same "take it if it doesn't overlap" logic produces a smaller, wrong answer, because it commits to a bad early choice before ever seeing 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 can't cost you the globally-best answer — Build It states each one. Skipping that check and just trusting the greedy instinct is how you end up with a fast, confident, wrong answer: it'll pass on the first three test cases you try it on and fail on the fourth.
Off-by-one on interval boundaries
If one activity ends exactly when the next one starts, are they overlapping or not? start >= lastEnd treats a shared boundary point as fine (back-to-back, non-overlapping); start > lastEnd would reject it. Both are defensible — but the problem statement picks one, and using the wrong comparison silently drops or admits one extra interval at every boundary case without ever throwing an error.
Sign in to mark problems done — progress syncs across devices.