Greedy

Six meetings want the same room. Fit as many in as you can.

Your instinct is a greedy one: grab a meeting, then the next one that fits, and keep going. The instinct is right. The hard part is that the same instinct is catastrophically wrong on a problem that looks almost identical — and nothing about the code tells you which case you are in.

Greedy in one sentence

Make the choice that looks best right now, never reconsider it.

That is it. There is no cleverness in the mechanism. All the difficulty is in answering one question: is a locally best choice part of a globally best answer?

Two problems, one instinct

Flip between them:

Scheduling: greedy is optimal, and provably so. Making change with coins 1, 3 and 4: greedy takes the 4, is left with 2, and pays with two 1s — three coins, where 3 + 3 does it in two.

Both problems are “repeatedly take the best-looking option”. One works. One does not. The code is equally short in both cases and equally confident.

The proof you owe

You are allowed to use greedy when you can make an exchange argument. It goes like this:

Take any optimal solution. Show that you can swap in the greedy choice without making it worse. Repeat, and the optimal solution turns into the greedy one — so greedy must be optimal too.

For meeting scheduling, the greedy choice is the meeting that finishes earliest. Suppose some perfect schedule starts with a different meeting. Replace it with the earliest-finishing one: it started no later, it ends no later, so it cannot conflict with anything that followed. The schedule is still valid and still the same size.

Now do the same to the rest. Every step, greedy’s choice can be substituted for free — so greedy reaches the same count.

Almost always, sorting is the algorithm

Notice what actually made scheduling work: sorting by end time. Sort by start time and you get a worse answer; sort by duration and you also get a worse answer, on a different input.

function maxMeetings(meetings: [start: number, end: number][]): number {
  const sorted = [...meetings].sort((a, b) => a[1] - b[1]);   // ← by END. This is the algorithm.

  let count = 0;
  let free = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= free) { count += 1; free = end; }
  }
  return count;
}

The loop is four lines and has no decisions in it. Every greedy algorithm looks like this: the intelligence is in the sort key, and choosing the wrong key is how greedy solutions fail.

Greedy that is provably correct

A short list worth knowing, because these come up constantly:

• Interval scheduling — earliest end time. Above.
• Huffman coding — repeatedly merge the two least frequent symbols. This is how every ZIP file and JPEG assigns bit lengths.
• Dijkstra’s algorithm — always settle the nearest unfinished node. The proof is an exchange argument, and it is why negative edges break it.
• Kruskal’s minimum spanning tree — take the cheapest edge that does not form a cycle, using union-find for the test.
• Fractional knapsack — best value per unit weight first. Note fractional: the 0/1 version, where items cannot be split, is not greedy at all and needs dynamic programming.

That last pair is the clearest warning in the list. Two problems, one word of difference, completely different techniques.

Greedy when it is not correct

Sometimes an approximate answer is worth having. Greedy set cover — repeatedly take the set covering the most uncovered elements — is guaranteed within a factor of $\ln n$ of optimal, and finding the true optimum is NP-hard. That is a good trade, made deliberately.

The mistake is not using greedy on a hard problem. The mistake is using it without knowing which of the two you are doing.

How to decide, in practice

1. Name the greedy choice. Not “be greedy” — the actual rule. “The meeting that ends first.” If you cannot state it in one sentence, you do not have an algorithm yet.
2. Try to break it. Spend two minutes actively hunting for a counterexample. Small ones: three items, two coins. This finds most bad greedy solutions faster than any amount of staring.
3. If you cannot break it, sketch the exchange. Does swapping your choice into an optimal solution keep it valid and no worse?
4. If the exchange fails, go to DP. The failure is usually informative — it tells you which piece of state the greedy version was ignoring, and that state is your DP key.

Step 2 is the one people skip, and it is the cheapest.