Day 27: Greedy Algorithms

DAY 27 / 30 · WEEK 4

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.

currently checking kept (non-overlapping) removed (overlaps last kept)

Non-overlapping Intervals (LC 435) — greedy sorted by end time

Press Play or Step to begin.

Step 0 / 0

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]])

Interval (sorted by end)	lastEnd before	start < lastEnd?	Action	removals after
[1,2] (first)	—	—	keep (nothing to compare against yet) — lastEnd = 2	0
[2,3]	2	2 < 2? No	keep — lastEnd = 3	0
[1,3]	3	1 < 3? Yes	remove (overlaps [2,3])	1
[3,4]	3	3 < 3? No	keep — lastEnd = 4	1

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

Approach	Time	Space	Why
eraseOverlapIntervals (full)	O(n log n)	O(log n) – O(n)	The sort dominates the runtime — the greedy scan after it is a single O(n) pass. Space depends on the sort implementation: some comparison sorts use O(log n) recursion stack, others (like some engines’ array sort) can use up to O(n) auxiliary space.
The greedy walk alone (already sorted)	O(n)	O(1)	One pass, tracking only `lastEnd` and a counter — no extra data structures.

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

1. Best Time to Buy and Sell Stock II

Easy — LeetCode: Best Time to Buy and Sell Stock II

Given daily stock prices, return the maximum profit you can make with unlimited transactions (buy then sell, any number of times, but you must sell before buying again). This is a different LeetCode problem from the single-transaction “Best Time to Buy and Sell Stock” from earlier in the course — this one allows as many trades as you want.

Show hint

You don’t need to track actual buy/sell days. Every day the price goes up compared to yesterday, that gain was available to capture — so just sum every positive day-over-day difference. Greedy works here because capturing every uptick is always at least as good as any other trading strategy.

Show solution

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;
}

2. Non-overlapping Intervals

Medium — LeetCode: Non-overlapping Intervals

Given a list of intervals, return the minimum number of intervals to remove so the rest don’t overlap. Today’s main worked example — the code above is the real solution.

Show hint

Sort by end time first — that single decision is what makes the rest of the algorithm correct. Then walk left to right, tracking the end time of the last interval you kept; any interval whose start is earlier than that gets removed.

Show solution

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;
}

3. Jump Game

Medium — LeetCode: Jump Game

Given an array where nums[i] is the maximum jump length from index i, starting at index 0, return whether you can reach the last index.

Show hint

Track the farthest index reachable so far as you scan left to right, updating it to max(farthest, i + nums[i]) at every index. If you ever reach an index that’s beyond the farthest point reachable BEFORE you update it at that index, you’re stuck — return false.

Show solution

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

What does the “greedy-choice property” mean?
- A. A locally optimal choice at each step is provably always part of some globally optimal solution
- B. The input must be sorted before a greedy algorithm can run
- C. Every optimization problem automatically has it
Answer
A. The greedy-choice property means a locally optimal choice at each step is PROVABLY always part of some globally optimal solution. It’s not a guarantee that comes from a problem “looking” like an optimization problem — it has to actually be proven (or disproven with a counter-example) for that specific problem.
In interval scheduling, why sort by END time instead of START time?
- A. Keeping the interval that finishes earliest leaves the most room for everything after it
- B. Sorting by end time is computationally faster than sorting by start time
- C. Start-time and end-time sorting always produce the same greedy result
Answer
A. Sorting by end time means whichever interval finishes earliest is always considered — and finishing earliest always leaves the maximum possible room for everything that comes after. Sorting by start time can lock in a “wide” interval early (like [1,10]) that blocks several shorter, non-overlapping intervals that would have been better to keep.
What does the coin-change counter-example (coins [1,3,4], amount 6) prove?
- A. Greedy’s locally-optimal choice isn’t always globally optimal — it can produce a worse answer than DP
- B. That dynamic programming gives the wrong answer for coin change
- C. That greedy only fails when the amount is very large
Answer
A. With coins [1,3,4] and amount 6, greedy (always take the largest coin) picks 4, then 1, then 1 — 3 coins — while the true optimum is 3+3, just 2 coins. Locally optimal did not lead to globally optimal, proving greedy isn’t always correct — it depends entirely on whether the greedy-choice property actually holds for that specific problem.
How do you recognize, in an interview, that a problem is NOT greedy-safe?
- A. You can construct any single counter-example where the greedy choice leads to a worse outcome
- B. Whenever the greedy solution runs slower than O(n)
- C. You can never know without submitting it and seeing if it fails
Answer
A. If you can construct even one input where the greedy choice leads to a worse outcome than the true optimum, greedy is not safe for that problem — that’s the rule of thumb. DP’s exhaustive subproblem consideration is the fallback when you can’t prove (or can actively disprove) the greedy-choice property.
What’s the time complexity of the Non-overlapping Intervals greedy solution?
- A. O(n log n) — dominated by the sort; the greedy scan itself is O(n)
- B. O(n) — sorting doesn’t affect the complexity
- C. O(n²) — every interval is compared against every other interval
Answer
A. The sort dominates the runtime at O(n log n); the greedy scan that follows it is only O(n). If the input were already guaranteed sorted by end time, the walk alone would be O(n) — but the algorithm as a whole, including the required sort, is O(n log n).