Greedy Algorithms Explained

Greedy is the simplest strategy there is: take the best thing available right now. It is also the easiest to get wrong, because a greedy solution that is subtly incorrect still returns a plausible answer.

The idea

At each step, make the choice that looks best in isolation. Never go back and reconsider. No cache, no table - usually just a sort and a single pass.

When it works it is faster and simpler than dynamic programming. The whole difficulty is knowing whether it works.

A case where it does

Interval scheduling: given meetings with start and end times, fit in as many as possible. Sort by end time and always take the next one that fits.

function maxMeetings(meetings) {
  // Earliest finishing first — that is the greedy choice.
  const sorted = [...meetings].sort((a, b) => a.end - b.end)

  let count = 0
  let lastEnd = -Infinity

  for (const meeting of sorted) {
    if (meeting.start >= lastEnd) {
      count++
      lastEnd = meeting.end
    }
  }

  return count
}

console.log(maxMeetings([
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 7 },
  { start: 6, end: 8 },
]))  // 3

Why does finishing earliest work? Because taking the meeting that ends soonest leaves the most room for everything after it, and no alternative choice can leave more. That argument is the proof - and if you cannot make an argument like it, the greedy approach is probably wrong.

A case where it does not

Coin change is the standard counterexample:

// Take the largest coin that fits, repeatedly.
function coinChangeGreedy(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a)
  let count = 0

  for (const coin of sorted) {
    while (amount >= coin) {
      amount -= coin
      count++
    }
  }

  return amount === 0 ? count : -1
}

// With [1, 5, 10, 25] greedy is correct — that is why it feels right.
console.log(coinChangeGreedy([1, 5, 10, 25], 30))  // 2, correct

// With [1, 3, 4] it is not.
console.log(coinChangeGreedy([1, 3, 4], 6))  // 3  (4 + 1 + 1)
// The real answer is 2  (3 + 3).

This is the trap. Greedy gives the right answer for ordinary currency, so it passes every test you would think to write - and then fails on a coin system you did not consider.

How to tell before you commit

1. Try to argue it. Can you say why the local best is always part of a global best? If the argument is hand-wavy, it is wrong.
2. Hunt for a counterexample. Deliberately try to build an input where taking the best now forces a worse outcome later.
3. Look for a trap door. If an early choice can block a better option that only appears later, greedy fails.
4. When unsure, use DP. It is slower and correct. A correct slow answer beats a fast wrong one.

Where greedy is reliably safe

• Interval scheduling - earliest end time.
• Minimising waiting time - shortest job first.
• Huffman coding - always merge the two smallest.
• Making change with canonical currency - but only because those systems are designed for it.