Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step without reconsidering past decisions. When the problem has the greedy-choice property — meaning a locally optimal choice leads to a globally optimal solution — greedy algorithms are faster and simpler than dynamic programming.

When Greedy Works

Two conditions must hold for greedy to be correct: greedy-choice property (a greedy choice is always part of some optimal solution) and optimal substructure (optimal solution contains optimal solutions to subproblems). If both hold, greedy gives the optimal solution. Otherwise, use DP or exhaustive search.

Activity Selection

Select the maximum number of non-overlapping activities. Greedy choice: always pick the activity that finishes earliest.

function activitySelection(activities) {
  // sort by finish time
  activities.sort((a, b) => a.end - b.end);
  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }
  return selected;
}

const acts = [{ start: 1, end: 4 }, { start: 3, end: 5 }, { start: 0, end: 6 }, { start: 5, end: 7 }];
activitySelection(acts); // [{start:1,end:4}, {start:5,end:7}]

Fractional Knapsack

Unlike 0/1 knapsack (requires DP), fractional knapsack allows taking fractions of items. The greedy approach — always take the highest value-per-weight item first — is optimal here.

function fractionalKnapsack(items, capacity) {
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let totalValue = 0;

  for (const item of items) {
    if (capacity >= item.weight) {
      totalValue += item.value;
      capacity -= item.weight;
    } else {
      totalValue += item.value * (capacity / item.weight);
      break;
    }
  }
  return totalValue;
}

Interval Scheduling — Minimum Platforms

Find the minimum number of platforms (rooms, threads, servers) needed so no two overlapping intervals share one.

function minPlatforms(arrivals, departures) {
  arrivals.sort((a, b) => a - b);
  departures.sort((a, b) => a - b);
  let platforms = 1, maxPlatforms = 1;
  let i = 1, j = 0;

  while (i < arrivals.length) {
    if (arrivals[i] <= departures[j]) { platforms++; i++; }
    else { platforms--; j++; }
    maxPlatforms = Math.max(maxPlatforms, platforms);
  }
  return maxPlatforms;
}

Huffman Coding

Huffman coding assigns shorter bit patterns to more frequent characters. Build a min-heap of frequencies, repeatedly merge the two smallest nodes. The result is an optimal prefix-free code.

// Conceptual — production uses a proper min-heap
function huffman(freq) {
  let heap = Object.entries(freq).map(([ch, f]) => ({ ch, f }));
  while (heap.length > 1) {
    heap.sort((a, b) => a.f - b.f);
    const left = heap.shift(), right = heap.shift();
    heap.push({ ch: left.ch + right.ch, f: left.f + right.f, left, right });
  }
  return heap[0]; // root of Huffman tree
}

Greedy vs Dynamic Programming

• Greedy: O(n log n) or O(n), no table, single pass — but only correct with greedy-choice property
• DP: Always correct for optimal-substructure problems, but O(n²) or more space/time
• Coin change with arbitrary denominations: greedy fails; DP required
• Coin change with standard denominations (1, 5, 10, 25): greedy works