DAY 27 / 30 · WEEK 4

Greedy Algorithms

Goal of the day

• Understand what "greedy" actually means: make the locally-optimal choice at every step and never revisit it — and learn the greedy-choice property, the one condition that must hold before that strategy is allowed to work.
• Work through Non-overlapping Intervals (LC 435) as a canonical example where greedy provably works — and understand precisely why sorting by end time (not start time, not interval length) is what makes the greedy choice safe.
• Work through a genuine counter-example — coin change with coins [1, 3, 4] — where greedy provably fails, to build the instinct for recognizing when NOT to trust it.

Concept

A greedy algorithm makes the choice that looks best right now, commits to it, and never looks back. No backtracking, no reconsidering, no comparing against alternatives you didn't take. Contrast that with dynamic programming (Days 25–26): DP considers — or caches the outcome of — every relevant subproblem, then combines those cached answers into a provably-correct result. Greedy skips all of that bookkeeping and just takes the best-looking option at each step. That makes greedy dramatically cheaper when it's valid... and silently wrong when it isn't.

"When it's valid" is the whole game. A greedy strategy is only safe to use when the problem has the greedy-choice property: the locally optimal choice at each step is provably always part of some globally optimal solution. If you can't prove that — or worse, if you can find even one input where the locally-best choice leads somewhere worse — greedy is not safe, and you need DP's exhaustive subproblem search instead.

Today has two worked examples that sit on opposite sides of that line:

• Non-overlapping Intervals — greedy works here. Sort the intervals by end time, then greedily keep any interval whose start doesn't overlap the last interval you kept. The insight that makes this provably correct: whichever interval finishes earliest always leaves the most possible room for everything that comes after it, so keeping it can never be a worse choice than keeping something that finishes later.
• Coin change with coins [1, 3, 4] — greedy fails here. "Always take the biggest coin you can" sounds locally reasonable, but for amount 6 it produces a demonstrably worse answer than the true optimum. This is the exact reason Day 26's Coin Change used DP instead of a greedy shortcut — greedy simply cannot be trusted on this problem shape.

Diagram: interval scheduling — greedy sorted by end time

Diagram: when greedy fails — coin change with [1, 3, 4], amount 6

Interactive visualization: the interval greedy walk

Watch Non-overlapping Intervals run step by step: sort by end time, then walk left to right, keeping anything that doesn't overlap the last kept interval.

The dashed blue line marks lastEnd — the boundary the next interval's start must clear to be kept.

The code

// Non-overlapping Intervals (LC 435) — greedy, sorted by END time.
// Returns the minimum number of intervals to remove so the rest don't overlap.
function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  // The single most important line: sort by END time, not start time.
  // Whichever interval finishes earliest leaves the most room for what follows —
  // that's the greedy-choice property holding for THIS ordering specifically.
  intervals.sort((a, b) => a[1] - b[1]);

  let removals = 0;
  let lastEnd = intervals[0][1];        // end time of the most recently KEPT interval

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (start < lastEnd) {
      removals++;                       // overlaps the last kept interval — discard it
    } else {
      lastEnd = end;                    // no overlap — this becomes the new "last kept"
    }
  }
  return removals;
}

// The classic counter-example: greedy does NOT work for arbitrary coin change.
// Coins [1, 3, 4], amount 6 — "always take the largest coin you can afford."
function greedyCoinChange(coins, amount) {
  const sorted = coins.slice().sort((a, b) => b - a); // largest first
  let remaining = amount;
  const picks = [];
  for (const coin of sorted) {
    while (remaining >= coin) {
      picks.push(coin);
      remaining -= coin;
    }
  }
  return picks; // for [1,3,4], amount 6 -> [4, 1, 1] — 3 coins, NOT optimal (3+3 = 2 coins)
}

Line by line:

• intervals.sort((a, b) => a[1] - b[1]) is the entire trick. Sorting by end time means the interval that finishes soonest is always considered first — and "finishes soonest" is exactly the property that makes a greedy keep-decision provably safe here.
• lastEnd tracks the end time of the most recently kept interval — it's the boundary the next interval's start has to clear.
• The loop starts at i = 1 because intervals[0] (the interval that finishes earliest of all) is always kept — there's nothing before it to overlap with.
• if (start < lastEnd) — this interval starts before the last kept one finished, so they overlap. Increment removals and move on; lastEnd does NOT change, because the interval that's already kept still ends earlier than this discarded one would have.
• else { lastEnd = end; } — no overlap, so this interval survives and becomes the new reference point for everything after it.
• greedyCoinChange is deliberately the "obviously reasonable" approach: sort coins largest-first, and keep taking the biggest one that still fits. It's included specifically to be traced against the diagram above and shown to be wrong for [1, 3, 4].

Dry run: eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])

Input [[1,2],[2,3],[3,4],[1,3]] sorts by end time to [1,2],[2,3],[1,3],[3,4]. Only [1,3] overlaps a kept interval — final answer: 1 removal.

Complexity

Interview corner

• Why sort by END time instead of START time? Keeping the interval that finishes earliest always leaves the maximum possible room for everything that comes after — that's what makes the greedy "keep" decision provably safe. Sorting by start time breaks this: consider [1,10], [2,3], [4,5]. Sorted by start, [1,10] comes first and gets kept (nothing to compare against yet), which then blocks both [2,3] and [4,5] — 2 removals. But the true optimum keeps [2,3] and [4,5] (they don't overlap each other) and removes only [1,10] — 1 removal. Start-time sorting can lock in a "wide" interval early and block everything else; end-time sorting never can, because it always prefers whatever frees up the earliest.
  ⚠ Trap: sorting by interval length has the same failure mode as sorting by start time — a short interval can still finish late and block a lot of what follows it. Length and start time both miss the one property that actually matters: when does it end.
• What does the coin-change counter-example (coins [1,3,4], amount 6) actually prove? That the greedy-choice property doesn't hold for arbitrary coin systems. "Always take the largest coin you can" picks 4, then 1, then 1 — 3 coins — while the true minimum is 3+3, just 2 coins. Locally optimal (biggest coin available) did not lead to globally optimal. Any time you can produce even one input like this, greedy is formally disqualified for that problem — this is the formal answer to "when does greedy fail."
  ↳ Common follow-up: "When does greedy actually work for coin change?" Only for canonical coin systems (like US currency: 1, 5, 10, 25) where it's provable that the largest-coin choice never blocks a better solution. You can't assume canonicity — you have to know or prove it for the specific coin set given.
• How do you recognize, in an interview, whether a problem is greedy-safe or needs DP? Try to construct a counter-example before committing to greedy: pick a small, adversarial input and hand-trace the greedy choice against what you know (or can compute) the true optimum to be. If you can find even ONE case where the greedy choice leads to a worse outcome, greedy is not safe — fall back to DP, whose exhaustive subproblem consideration is exactly the guarantee greedy doesn't have.
  ⚠ Trap: "it passed the example in the problem statement" is not proof — the coin-change counter-example above would pass plenty of small test cases (e.g. amount = 4 → greedy correctly picks [4], or [3,1]) while still being wrong on amount = 6. One passing example never proves the greedy-choice property.
• How does this connect to Day 26's Coin Change DP? Same problem shape — minimum coins to make an amount — with two totally different guarantees. Yesterday's DP solution considers every reachable sub-amount and keeps the true minimum at each one, so it's correct for any coin system, canonical or not. Today's greedy shortcut is faster and simpler to write, but only correct when the specific coin set happens to have the greedy-choice property — and [1, 3, 4] is the concrete proof that you can't assume that. DP is the safe default; greedy is the fast path you're only allowed to take once you've proven it's safe.

How to talk through it out loud: state the greedy choice explicitly before writing any code — "I'll sort by end time and keep whatever doesn't overlap the last kept interval" — then say why it's safe: "the earliest-finishing interval always leaves the most room, so this choice can't be wrong." If you're not sure a greedy choice is safe, say so out loud and propose testing it against a small adversarial example before committing — that's exactly the instinct interviewers are listening for, and it's the difference between "I got lucky" and "I can prove this is correct."

Practice problems

function maxProfit(prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
}

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[1] - b[1]);
  let removals = 0;
  let lastEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (start < lastEnd) {
      removals++;
    } else {
      lastEnd = end;
    }
  }
  return removals;
}

function canJump(nums) {
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

Quiz