Greedy algorithms

The trade greedy makes

DP explores every relevant option and keeps whichever turns out best. Greedy skips that entirely: at each step, take whatever looks best right now, commit to it, and never reconsider. That's a huge shortcut when it works — usually O(n log n) instead of DP's O(n²) or worse — but it only produces the correct answer for problems with a specific mathematical property.

The property that has to hold: the greedy-choice property

A problem is safe for greedy only if a locally optimal choice is always part of some globally optimal solution — choosing it never closes off the best overall answer. If that's not provably true, greedy will find a valid answer, just not always the best one, and it will fail silently — no error, just a wrong result on some input you didn't test.

Worked example: Activity/Interval scheduling

Maximize the number of non-overlapping intervals you can select. The greedy choice: always take the interval that finishes earliest among the remaining valid options.

function maxNonOverlapping(intervals) {
  intervals.sort((a, b) => a[1] - b[1]); // sort by FINISH time — the entire trick

  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of intervals) {
    if (start >= lastEnd) { // this one doesn't conflict with our last pick
      count++;
      lastEnd = end;
    }
  }
  return count;
}

Why finish time and not start time or duration: picking whatever finishes earliest leaves the maximum possible room for everything that comes after — any other choice can only leave equal or less room. That's the actual proof sketch, and being able to say it is what separates "I memorized this" from "I understand why it's safe."

Worked example: Jump Game — can you reach the end?

function canJump(nums) {
  let farthestReachable = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthestReachable) return false; // stuck — can't even reach index i
    farthestReachable = Math.max(farthestReachable, i + nums[i]);
  }
  return true;
}

The greedy insight: you never need to know which path gets you furthest, only the single number "furthest index reachable so far" — tracking every possible path (which DP would do) is unnecessary work because only the maximum ever matters for future decisions.

Worked example: Gas Station

function canCompleteCircuit(gas, cost) {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {       // can't reach the next station from any point up to here
      start = i + 1;       // so the answer, if any, must start AFTER i
      tank = 0;
    }
  }
  return total >= 0 ? start : -1; // total < 0 means no valid start exists anywhere
}

This one's greedy argument is subtler: if the tank goes negative arriving at station i, starting from any station between the current start and i would also fail, because each of those partial sums was non-negative up to the point of failure — so it's always safe to jump the candidate start forward to i + 1 without missing a valid answer.

Greedy vs DP — how to decide which one a problem wants

Recognizing it in an unseen problem

• "Minimum number of," "maximum number of," where a sorted, greedy-order decision seems natural
• You can articulate why the greedy choice never eliminates the optimal answer — if you can't, don't trust it
• Scheduling, interval, and "assign resources" problems are greedy's home turf
• When in doubt in an interview: try to prove greedy for a minute; if you can't, say so and switch to DP rather than silently guessing