Greedy and backtracking

Greedy: commit, and never reconsider

A greedy algorithm makes the locally best choice and never revisits it. It is usually short, usually fast — O(n log n) here, all of it the sort — and usually wrong.

This one is right, and it has a proof: the meeting that finishes earliest leaves the most room for everything after it, so there is always an optimal schedule that starts with it. That exchange argument is what separates a greedy algorithm from a guess.

the most meetings you can attend

function maxMeetings(meetings) {
  const byEnd = [...meetings].sort((a, b) => a.end - b.end);   // earliest finish first
  let count = 0;
  let free = -Infinity;

  for (const m of byEnd) {
    if (m.start >= free) { count++; free = m.end; }
  }

  return count;
}

When greedy fails

Taking the biggest coin first is optimal for the coins in your pocket — that is a property of those denominations, not of the strategy. Change the set and the same algorithm quietly returns a worse answer, with no error and no warning.

The test is always: can an early choice be regretted? If yes, greedy is unsound and you need DP (which considers every combination efficiently) or a search (which considers them explicitly).

text

coins [1, 3, 4], make 6

greedy:  4 + 1 + 1   =  3 coins
best:    3 + 3       =  2 coins

Where greedy is provably right

The last two rows are the same problem with one difference: if you may take half an item, greedy is optimal; if each item is all or nothing, it is not. That is how narrow the line is.

Problem	The greedy rule
Interval scheduling	Earliest finishing time first
Huffman coding	Merge the two rarest symbols
Minimum spanning tree (Kruskal, Prim)	The cheapest edge that does not close a cycle
Dijkstra	Expand the nearest unfinished node — the last lesson
Fractional knapsack	Best value per kilogram first
0/1 knapsack	No greedy rule works. This one needs DP

Backtracking: try, and undo

Choose, explore, undo. The undo is what makes it backtracking rather than brute force: one array is reused for the whole search instead of a copy per branch, so the memory is the depth rather than the number of results.

every permutation, with one array

function permutations(items) {
  const out = [];
  const current = [];
  const used = new Array(items.length).fill(false);

  const go = () => {
    if (current.length === items.length) { out.push([...current]); return; }

    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;

      used[i] = true; current.push(items[i]);     // choose
      go();                                       // explore
      current.pop(); used[i] = false;             // UNDO — this is the backtrack
    }
  };

  go();

  return out;
}

Pruning is what makes it finish

Eight queens has 8⁸ ≈ 16.7 million placements if you generate then filter, and about 2 000 nodes if you reject each illegal square as you reach it. Same answer, four orders of magnitude apart.

That is the whole engineering of backtracking: the search is exponential, and every branch you can rule out early removes a whole subtree. The trie lesson made the same point about startsWith — being able to say "nothing can come of this" is worth more than the lookup.

n-queens: reject a placement before recursing, not after

const safe = (cols, row, col) =>
  cols.every((c, r) => c !== col && Math.abs(c - col) !== Math.abs(r - row));

const place = (cols) => {
  if (cols.length === n) { solutions++; return; }
  for (let col = 0; col < n; col++) {
    if (!safe(cols, cols.length, col)) continue;     // ← the prune
    cols.push(col);
    place(cols);
    cols.pop();
  }
};

Greedy: commit, and never reconsider

When greedy fails

Where greedy is provably right

Backtracking: try, and undo

Pruning is what makes it finish

Practice