Greedy Algorithms

A greedy algorithm builds its answer by always taking the choice that looks best *right now* and never going back to revise it. That's fast and simple — but it only reaches the true optimum for special problems. The skill is knowing which ones, and *proving* the greedy choice is safe.

Worked example — activity selection

Given activities with fixed [start, end] times, pick the most that don't overlap. Take [1,3], [2,5], [4,7], [6,9], [8,10]. The winning rule is sort by finish time, then repeatedly grab the earliest-ending activity that starts at or after your last pick's end: choose [1,3], skip [2,5] (starts at 2 < 3), choose [4,7], skip [6,9], choose [8,10] — three activities, the maximum possible.

1. 1Sort all activities by their end time.
2. 2Track lastEnd, the finish of the most recent pick (start it at −∞).
3. 3Scan in order: if an activity's start ≥ lastEnd it doesn't overlap — take it and update lastEnd.
4. 4Otherwise skip it and move on. The activities you kept are a maximum-size non-overlapping set.

function selectActivities(acts) {
  acts.sort((a, b) => a.end - b.end); // sort by finish time
  const chosen = [];
  let lastEnd = -Infinity;
  for (const a of acts) {
    if (a.start >= lastEnd) {  // doesn't overlap the last pick
      chosen.push(a);
      lastEnd = a.end;
    }
  }
  return chosen;
}

Why it's optimal — the exchange argument

Let g be the activity that finishes earliest — greedy's first pick. Take *any* optimal schedule O and look at its first activity a. Since g finishes no later than a (it finishes earliest of all), we can swap a out and g in: g ends no later than a did, so it can't clash with anything else in O. The swapped schedule has the same number of activities, so it's still optimal — and now it contains greedy's choice. Repeat on the rest and greedy matches an optimal solution every time.

When greedy fails

Greed reaches the optimum only when an exchange argument holds. Make change for 6 using coins [1, 3, 4] by always grabbing the biggest coin that fits: 4, then 1, then 1 — three coins. But 3 + 3 needs only two. The same trap hits the 0/1 knapsack: with capacity 50 and items (w10, v60), (w20, v100), (w30, v120), taking the best value-per-weight first gives value 160, while 100 + 120 = 220 is the real best. Those problems need dynamic programming, not greed.