What a greedy algorithm is
Your calendar shows five meeting requests —
[1,3], [2,4], [3,5], [5,7], [6,8] — some overlapping. You want to attend as many as possible. Trying every subset of meetings is O(2ⁿ) (from the Backtracking lesson: the include-or-skip decision tree). But this problem has a shortcut hiding in plain sight.A greedy algorithm builds the answer one step at a time, always taking the choice that looks best right now, and — this is the defining part — never undoing it. No branching, no backtracking, no table of subproblems. One sorted sweep.
That only works when the problem has a special property: the local best choice can never cost you the global best. The standard way to convince yourself is the exchange argument — a swap-based proof sketch: take any optimal answer; swap its first choice for the greedy choice; show nothing was lost. For the meetings, the greedy choice is the meeting that ends earliest — any optimal plan's first meeting can be swapped for it, because ending earlier can only leave more room for the rest.
Greedy sits between two neighbours you know: unlike backtracking it never explores alternatives, and unlike dynamic programming (the final stop of this course) it never revisits a subproblem. When it applies, it is the fastest of the three — and when it doesn't, it is confidently wrong.
Quick check
What separates greedy from backtracking?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
The meetings problem, solved greedily. The insight: to leave the most room for future meetings, always keep the one that frees you earliest.
The steps
- Sort by end time — the meeting ending soonest comes first.
- Sweep once, tracking
freeAt— when your current commitment ends. - A meeting that starts at or after
freeAtfits: take it, updatefreeAtto its end. - Anything that starts earlier clashes with what you kept: skip it, permanently.
Trace it on [1,3], [2,4], [3,5], [5,7], [6,8] (already sorted by end)
| meeting | starts vs freeAt | decision | freeAt after |
|---|---|---|---|
| [1,3] | 1 ≥ −∞ | take | 3 |
| [2,4] | 2 < 3 | skip | 3 |
| [3,5] | 3 ≥ 3 | take | 5 |
| [5,7] | 5 ≥ 5 | take | 7 |
| [6,8] | 6 < 7 | skip | 7 |
Three meetings — and no subset does better. Why skipping
[2,4] is safe: it ends at 4, later than the [1,3] you kept, so anything [2,4] would leave room for, [1,3] leaves room for too. That's the exchange argument doing its job on a concrete pair.In the animation, watch each meeting turn green (taken) or fade (skipped) as the sweep compares its start against
freeAt — and notice the skips never come back. In JavaScript:This section has a step-by-step animation in the interactive lesson.
function maxMeetings(meetings) {
const byEnd = [...meetings].sort((a, b) => a[1] - b[1]);
let count = 0;
let freeAt = -Infinity;
for (const [start, end] of byEnd) {
if (start >= freeAt) {
count++; // take it — earliest to finish
freeAt = end;
}
}
return count;
}
console.log(maxMeetings([[1,3],[2,4],[3,5],[5,7],[6,8]])); // 3Quick check
Meetings sorted by end: [1,4], [2,5], [4,6]. Predict the greedy result.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
Greedy fails confidently — it always produces an answer, just not always the best one. The two classic traps:
- No exchange argument = no guarantee. Coin change with coins
[1, 3, 4], target6: greedy grabs the biggest coin first —4 + 1 + 1= 3 coins — but the optimal is3 + 3= 2 coins. Taking the 4 did hurt the global answer, so greed is simply wrong here. (US coins[25, 10, 5, 1]happen to be greedy-safe — the coin system decides, not the algorithm.) When choices interact like this, you need dynamic programming — this course’s final lesson. - The right rule matters, not just "a" rule. Sort the meetings
[1,10], [2,3], [4,5]by start and greedily take: you grab[1,10]and nothing else fits — answer 1. Sorting by end takes[2,3]then[4,5]— answer 2. Both are greedy; only one has the proof. - Greedy silently assumes sorted input. Most greedy rules begin with a sort; feed unsorted data to the sweep and the answers are garbage with no error thrown.
Quick check
Coins [1, 3, 4], target 6. Predict greedy (biggest coin first) vs optimal.
Answer it in the interactive lesson to keep your progress.
Take it further — jump game
A different greedy flavour: no sorting, just a single number carried through one pass. In
nums = [2, 3, 1, 1, 4] each value is the maximum jump length from that index. Can you reach the last index?The greedy insight: all that matters is the farthest index reachable so far — call it
reach. How you got there is irrelevant.Trace it
| i | value | i + value | reach after |
|---|---|---|---|
| 0 | 2 | 2 | 2 |
| 1 | 3 | 4 | 4 — covers the last index |
Done at index 1 —
reach already covers index 4. And the failing case [3, 2, 1, 0, 4]: reach grows 3, 3, 3, 3… then index 4 is beyond reach — stranded, false.In the animation, watch the
reach marker: each index either pushes it farther or leaves it alone, and the moment the sweep arrives at an index past the marker, the answer is no. Before each step, predict whether reach moves.This section has a step-by-step animation in the interactive lesson.
function canJump(nums) {
let reach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > reach) return false; // stranded before reaching i
reach = Math.max(reach, i + nums[i]);
}
return true;
}
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // falseQuick check
nums = [1, 0, 5]. Predict canJump's verdict and where it decides.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, greedy's price is usually the sort:
| Approach | Time | Space |
|---|---|---|
| try every subset | O(2ⁿ) | O(n) |
| greedy: sort + sweep (meetings) | O(n log n) | O(1) |
| greedy: single pass (jump game) | O(n) | O(1) |
Key takeaways:
- Greedy = best local choice, kept forever — no undo, no revisit.
- It needs a proof: the exchange argument (swap the optimal's choice for yours; show nothing is lost).
- Interval scheduling sorts by end; reach problems carry one farthest number.
- When local choices interact (coins [1,3,4]), greed fails — that is dynamic programming's territory.
The same instinct powers a family of classics, each its own lesson later (no need to know them yet): jump game II (fewest jumps — this topic's Level-2 challenge), gas station (a running tank that resets), assign cookies (two sorted pointers), and non-overlapping intervals (the meetings rule, counting removals). Next up in order: Binary Search on the Answer — guessing the answer and letting a feasibility check steer the search.