Greedy Algorithms — When Local Best Is Global Best

Greedy = at every step, take the choice that looks best right now, never reconsider. When it works it's beautifully simple; the skill is knowing when it works.

The flagship: activity selection

"Maximum number of non-overlapping meetings?" Greedy choice: always pick the meeting that ends earliest.

function maxMeetings(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);   // sort by END time
  let count = 0, freeAt = -Infinity;
  for (const [start, end] of intervals) {
    if (start >= freeAt) { count++; freeAt = end; }
  }
  return count;
}

Why earliest end? Finishing sooner leaves maximum room for future meetings — the local choice provably never hurts the global outcome. That "never hurts" property is what makes greedy valid.

Jump Game — greedy disguised as DP

// Can you reach the last index? (nums[i] = max jump length)
let reach = 0;
for (let i = 0; i < nums.length; i++) {
  if (i > reach) return false;         // stranded before reaching here
  reach = Math.max(reach, i + nums[i]); // greedily extend the frontier
}
return true;

Track the furthest reachable frontier in one pass — O(n), no DP table needed.

Greedy vs DP — the interview question

• Greedy works when the local choice can be proven safe (exchange argument): activity selection, jump game, assigning cookies, gas station.
• Greedy fails when an early "best" blocks a better future: coin change with coins {1, 3, 4} for amount 6 — greedy takes 4+1+1 (3 coins), optimal is 3+3 (2 coins). That's why coin change is DP.

The honest interview answer: "I'd try greedy with a sort by X; if I can't argue the local choice is always safe, I'd fall back to DP." Showing you know greedy needs justification is the senior move.

Spot it when…

• Scheduling/intervals with "maximum number of…", resource assignment, "minimum number of platforms/arrows/taps".
• The array can be sorted so one sweep with a simple rule solves it.