Skip to content

level 8 · Core techniques

Greedy Algorithms

Always take the best-looking option right now — and sometimes that's provably optimal.

11 min 90 XP

what is it

Start here

A greedy algorithm never looks ahead. At every step it grabs whatever looks best right now, commits to it, and never reconsiders. It sounds far too naive to work — and usually it doesn't.

But sometimes it's *provably* optimal, and then it's wonderful: no table, no recursion, no backtracking. One pass, done.

Take the classic: one meeting room, lots of overlapping requests, fit in as many as possible. Which do you pick? 'The shortest meeting' feels right — and is wrong. 'The one that starts earliest' is wrong. The winner is **the one that finishes earliest** — because finishing early leaves the most room for everything else. You can never regret that choice, and that's exactly what makes it safe.

That phrase is the whole technique: a greedy algorithm works only when you can prove the local choice is never something you'd want to undo. When you can't prove it, the greedy answer is just a plausible guess — and you need dynamic programming instead.

You already saw greedy fail. With coins 1, 3 and 4, making 6: greedy grabs the biggest coin, 4, then needs 1 + 1 — three coins. The real answer is 3 + 3, just two. Same problem shape, and greedy walks straight past the optimum.

real-life analogy

Picture it

Booking a meeting room

Requests are stacking up and they clash. You take the one that ENDS soonest, because it hands the room back earliest, which leaves the most time for everything after it. Whatever else you might have picked instead, it would have freed the room later — so it could never do better.

interactive visualization

Watch it run

Each bar is a meeting's end time, sorted. Green ones got the room.

  1. 3
  2. 4
  3. 5
  4. 6
  5. 8
  6. 10
  7. 12

One room, many meetings, and they overlap. Fit in as many as possible. The bars are the meetings, sorted by when they END — and that sort is the entire algorithm.

step 01/14

  • comparing
  • in final place
  • found it
1// Fit as many meetings as possible into one room.
2function maxMeetings(meetings) {
3 // The greedy choice: always take the one that ENDS soonest.
4 meetings.sort((a, b) => a.end - b.end);
5
6 const chosen = [];
7 let lastEnd = 0;
8
9 for (const m of meetings) {
10 if (m.start >= lastEnd) {
11 chosen.push(m);
12 lastEnd = m.end;
13 }
14 }
15 return chosen;
16}

variables right now

meetings
7
comparisons 0moves 0

the dry run · every step, in words

14 steps

complexity

What it costs

best case
O(n log n)
average
O(n log n)
worst case
O(n log n)
extra memory
O(1)

The sort dominates — n log n — and then a single O(n) pass. Compare that with dynamic programming, which would have to build a table. When greedy is provably safe, it's dramatically simpler and faster.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n) · this one
  • O(n²)
input size →work →

common mistakes

Common traps

  • Assuming greedy works because it feels right.

    It needs proof. 'Take the shortest meeting' feels just as sensible as 'take the one ending soonest' — and it's wrong. Without an exchange argument, greedy is only a guess.

  • Using greedy on coin change.

    With coins 1, 3, 4 and a target of 6, greedy takes 4+1+1 = three coins; the real answer is 3+3 = two. Greedy fails; DP is required.

  • Sorting by the wrong key.

    For meetings, sort by *end* time, not start time and not duration. The whole correctness rests on that one choice.

  • Reconsidering an earlier choice.

    Then it isn't greedy any more — that's backtracking or DP. Greedy's speed comes precisely from never looking back.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+90 XP

01To fit the most meetings into one room, which do you always pick next?

02When is greedy the wrong tool?

03What does a greedy algorithm never do?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.