Stop 21 · Data Structures & AlgorithmsTopics · 14/17

Greedy

In short

Greedy means grabbing the best-looking option at each step and never looking back. Sometimes it's the perfect answer. Sometimes it's confidently wrong, and the trick is knowing which.

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

The jaadu picks the biggest coin from a tray to hand over as change.

Think of it like this

Giving change with Indian coins

For ₹18 change, the shopkeeper hands the biggest coin that fits first: ₹10, then ₹5, ₹2, ₹1. With our coins, that always uses the fewest. With odd coins like ₹1, ₹3 and ₹4, it can fail.

Watch it happen

Most meetings in one room

1-3

2-5

4-6

6-8

5-9

1/6Sort by end time: 1-3, 2-5, 4-6, 6-8, 5-9. lastEnd starts at -Infinity.

The big ideas

What you need to know

Best local choice

At each step, take what looks best right now. No going back, no trying alternatives.

Usually sort first

Many greedy solutions sort by end time, deadline or value, then make one pass. That's O(n log n).

Try to break it

Before coding, test a few small examples. If one counterexample beats your greedy, you need DP.

Fast and simple when it works

Greedy answers are short and quick, which is why interviewers like asking if one applies.

See it in code

Walk through the code

1// meetings: [[start, end], ...]2function maxMeetings(meetings) {3  const sorted = [...meetings].sort((a, b) => a[1] - b[1]);4  let count = 0;5  let lastEnd = -Infinity;6 7  for (const [start, end] of sorted) {8    if (start >= lastEnd) {9      count++;10      lastEnd = end;11    }12  }13  return count;14}

1/4Sort a copy by end time. This is the O(n log n) part.

Sorting is O(n log n) and the loop is O(n), so O(n log n) overall. Picking the earliest finish always leaves the most room for later meetings.

Save yourself the pain

Common mistakes

Oops

Assuming greedy works for coin change with any set of coins.

Do this instead

With coins 1, 3 and 4, greedy pays 6 as 4+1+1. The best is 3+3. Use DP for general coin sets.

Oops

Sorting meetings by start time or by length.

Do this instead

Sort by end time. Try a small counterexample to see why the others fail.

Your mission

Greedy or not?

~35 min

Quick check

Coins are 1, 3 and 4. A greedy algorithm (biggest coin first) pays 6. How many coins does it use, and is that the best?

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.