Stop 21 · Data Structures & AlgorithmsTopics · 14/17

Greedy

In short

Greedy algorithms grab the best-looking option right now and never look back. When it works, the code is tiny. The real skill is knowing when it doesn't.

An algorithmic approach that makes the locally optimal choice at each step, hoping (and sometimes provably) it leads to a globally optimal solution.

The purple blob shopkeeper hands change, picking the biggest coin first.

Think of it like this

The kirana shopkeeper's change

You pay ₹100 for an ₹13 item. Uncle gives ₹87 back by reaching for the biggest note that fits first: 50, then 20, then 10, 5 and 2. He never plans ahead, yet ends up with the fewest notes and coins.

Watch it happen

Making ₹87 with the fewest notes

1/5₹87 left. The biggest that fits is 50. Take it: ₹37 left.

The big ideas

What you need to know

Pick the local best

At every step, take the choice that looks best right now, and never undo it.

Usually sort first

Most greedy solutions start by sorting, by end time, by size or by ratio, so the best choice is easy to find.

It can be wrong

With coins 1, 3 and 4, greedy makes 6 as 4 + 1 + 1. The best is 3 + 3. Then you need DP.

Argue why it works

In interviews, explain why the greedy choice is safe, for example "finishing earliest leaves the most room".

See it in code

Walk through the code

1type Meeting = { start: number; end: number };2 3function maxMeetings(meetings: Meeting[]): number {4  const sorted = [...meetings].sort((a, b) => a.end - b.end);5  let count = 0;6  let freeAt = -Infinity;7 8  for (const m of sorted) {9    if (m.start >= freeAt) {   // fits after the last chosen meeting10      count++;11      freeAt = m.end;          // greedy: always pick the earliest finish12    }13  }14  return count;15}

1/3Sort by end time, so the meeting that frees the room soonest comes first.

How many meetings can one room hold? Sorting by end time and always taking the earliest-finishing meeting is provably optimal.

Save yourself the pain

Common mistakes

Oops

Using greedy for any "minimum coins" question.

Do this instead

Test a small odd case, like coins [1, 3, 4] and amount 6. If greedy fails, switch to dynamic programming.

Oops

Sorting meetings by start time or by length.

Do this instead

Sort by end time. Short or early-starting meetings can still block the room longer.

Your mission

Greedy or not?

~35 min

Quick check

Coins are 1, 3 and 4. Greedy makes 6 as 4 + 1 + 1. What does this show?

Go deeper

1Solve a classic greedy problem: activity selection or coin change (with certain coin sets).
2Learn to recognize when greedy actually works vs when it gives a wrong answer.
3Compare a greedy solution to a DP solution for the same problem when greedy fails.