Greedy Algorithms

Definition

A greedy algorithm builds a solution one decision at a time, at each step choosing whatever option looks best right now, and never reconsidering that choice later. It never backtracks and never explores alternatives once a choice is made, which makes greedy algorithms simple to implement and often very fast, typically O(n log n) or O(n), since each step just picks the best available option, often after a single sort. Greedy only produces a truly optimal answer when the problem has the greedy-choice property: making the locally best choice at every step must be provably part of some globally optimal solution. Many classic problems do have this property, such as picking the activity that finishes earliest first when scheduling non-overlapping intervals, or Huffman coding, which repeatedly merges the two least frequent symbols. Many others do not. The classic counterexample is coin change with arbitrary denominations: with coins of 4, 3, and 1 to make 6, greedy takes the biggest coin that fits at each step, 4 then 1 then 1, using 3 coins, but the optimal answer, 3 plus 3, only needs 2. Because greedy commits to 4 immediately without checking whether a different first choice could lead to a better total, it never even considers picking 3 twice.

Examples

function maxActivities(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) { count++; lastEnd = end; }
  }
  return count;
}
maxActivities([[1, 3], [2, 4], [3, 5], [6, 7]]); // 3

function greedyChange(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a);
  const used = [];
  let remaining = amount;
  for (const c of sorted) {
    while (c <= remaining) { used.push(c); remaining -= c; }
  }
  return used;
}
greedyChange([4, 3, 1], 6); // [4, 1, 1], 3 coins; optimal is [3, 3], 2 coins

function fractionalKnapsack(items, capacity) {
  const sorted = [...items].sort((a, b) => b.value / b.weight - a.value / a.weight);
  let total = 0, left = capacity;
  for (const item of sorted) {
    if (left <= 0) break;
    const take = Math.min(item.weight, left);
    total += take * (item.value / item.weight);
    left -= take;
  }
  return total;
}

Key takeaways

• Greedy algorithms commit to the best-looking choice at each step and never reconsider it.
• They are only guaranteed optimal when the problem has the greedy-choice property, proven for that specific problem.
• Coin change with arbitrary denominations like 4, 3, 1 is the classic counterexample: greedy can use more coins than necessary.
• Activity selection, Huffman coding, and minimum spanning trees are classic problems where greedy is provably optimal.

Where you see this

• Scheduling the maximum number of non-overlapping meetings or activities in a shared room.
• Building a Huffman coding tree for lossless data compression.
• Making change with well-behaved currency denominations, like US coins, where greedy happens to be optimal.
• Minimum spanning tree algorithms such as Kruskal's and Prim's, which greedily add the cheapest edge that keeps the tree valid.