HANDS-ON · 60 minutes
When greedy is provably correct and when it quietly fails — interval scheduling, jump game, and the exchange argument grounded in Brandon's job scheduler.
Greedy algorithms are the category where you'll write something confident, it'll pass every small test you throw at it, and then fail an edge case you didn't anticipate. The idea — always pick the locally optimal choice — produces correct answers on some problems and silently wrong answers on others. The difference is not just a gut feeling; it requires a proof that the greedy choice never prevents a globally optimal solution. In practice you will rarely write a formal proof, but you should be able to articulate the argument in one sentence before you trust a greedy solution. Without that, you're just hoping.
The clearest example of a correct greedy: interval scheduling maximization. Given a set of intervals, pick the maximum number that do not overlap. The greedy choice is always the interval with the earliest end time. Why does this work? Because finishing earlier leaves the most room for subsequent intervals — any other choice can only do worse or equal. That single sentence is the exchange argument, and it is the model for how to think about any greedy claim.
In my Python orchestration framework, I used Earliest Deadline First ordering for tasks with equal resource cost. EDF is textbook-correct for that specific formulation. The lesson: greedy works when the exchange argument holds — and stating the argument explicitly, before writing code, is the discipline that separates a correct greedy from a confident mistake.
Maximum non-overlapping intervals: sort by end time, greedily keep each interval whose start is after the last kept interval's end.
gantt
title Interval Scheduling — Earliest End Time Greedy
dateFormat X
axisFormat %s
section Intervals
A [1,3] : 1, 3
B [2,4] : 2, 4
C [3,5] : 3, 5
D [6,8] : 6, 8
section Kept (greedy)
A kept : 1, 3
C kept : 3, 5
D kept : 6, 8Sort by end: A ends at 3, C ends at 5, D ends at 8, B ends at 4. Greedy keeps A (last_end=3), then C (start=3 >= 3, last_end=5), then D (start=6 >= 5). B is skipped because it starts at 2, which is before A's end of 3. Count = 3.
Jump Game I: nums[i] is the max jump from index i. Can you reach the last index? Track the farthest reachable index as you walk left to right.
Analogy — the farthest flashlight: you are walking a dark corridor and holding a flashlight that illuminates as far as your current jump can reach. At each step, you extend the flashlight's range as far as the current position allows. When you reach the end of the current flashlight beam, you must make a jump — which resets the beam to the farthest point you found while walking. The number of resets is the minimum jumps.
Greedy fails when a locally optimal choice prevents a globally better one. Three patterns where this happens:
1. Arbitrary coin denominations. Denominations [1, 3, 4], target 6. Greedy picks 4+1+1 = 3 coins. Optimal is 3+3 = 2 coins. The exchange argument breaks because no single coin dominates all combinations.
2. 0/1 Knapsack. Items have weight and value; bag has capacity W. Greedy by value/weight ratio fails when the highest-ratio item leaves a gap that lower-ratio items would fill more profitably. DP (considering each item's include/exclude decision) is required.
3. Longest increasing subsequence. Greedy "always extend with the smallest available element" fails on subsequences (vs substrings). Use patience sorting (O(N log N) with bisect) or full DP.
When this bites: the greedy-vs-DP decision matters most at problem identification time, not at implementation time. If you write a greedy solution for coin change with arbitrary denominations, it will pass small test cases and fail on the edge case that breaks the exchange argument. Always state the exchange argument before committing to greedy.
Quick decision rule: if the problem has arbitrary weights or values where no item dominates all others, or if the problem asks to optimize across a combination of items with heterogeneous costs, reach for DP first. If you can articulate why the locally optimal choice is always globally safe in one sentence, greedy may apply.
Close the code and try these from memory:
Reflective prompt: My job scheduler uses EDF (Earliest Deadline First) greedily. But what if tasks have different resource costs — some tasks use 1 GPU, others use 4? EDF is no longer provably optimal. Think about what changes in the problem structure that breaks the exchange argument, and what alternative approach you would reach for.
Application-level questions on the exchange argument, interval scheduling, and jump game
1. The exchange argument for interval scheduling says: always pick the interval with the earliest end time. Why does this guarantee the maximum number of non-overlapping intervals?
Correct Answer: B
The exchange argument: suppose you chose interval A instead of B, where B ends earlier. You can always swap A for B without losing any valid subsequent interval — and B might enable intervals A would block. Therefore the earliest-end-time choice never hurts and sometimes helps.
2. Jump Game I: nums[i] is the max jump from index i. Can you reach the last index? What does a linear greedy track?
Correct Answer: B
Track `farthest = max(farthest, i + nums[i])` at each index i. If at any point i > farthest, you are stuck. If farthest >= n-1 at any point, you can reach the end. This single pass is O(N).
3. Coins = [1, 3, 4], target = 6. The greedy (pick largest coin first) gives how many coins, and what is the actual minimum?
Correct Answer: B
Greedy picks 4 first (largest <= 6), then 1+1 to make 6 — total 3 coins. DP finds 3+3=2 coins. This is the textbook greedy failure: arbitrary denominations break the exchange argument.
4. Which of the following is a reliable signal that greedy will NOT work and DP is needed?
Correct Answer: B
Arbitrary weights or values mean no single local choice is always safe — a heavier item might block several lighter ones that together have more value. This violates the exchange argument. Problems with arbitrary coin denominations, arbitrary item weights, or paths with arbitrary costs all require DP.
5. Jump Game II asks for the minimum number of jumps. The greedy maintains 'current_end' and 'farthest'. What triggers incrementing the jump count?
Correct Answer: B
current_end is the farthest you can reach with the current number of jumps. When i == current_end, you have exhausted that jump's range and must jump again. Set current_end = farthest and increment jumps. This greedy is correct because always extending to farthest minimizes future jumps needed.
6. You have N tasks, each with a deadline and equal cost. To maximize on-time completions, you should schedule them in what order?
Correct Answer: B
Earliest Deadline First is a provably optimal greedy for maximizing on-time completions when all tasks have equal cost. The exchange argument: if task A has a later deadline than B but runs before B, swapping them can only keep B on time and never makes A miss its deadline (A's deadline is later).
Problem: Jump Game II — given nums where nums[i] is the maximum jump from index i, return the minimum number of jumps to reach the last index. Assume you can always reach the last index.
Hint 1: Think of the jumps as BFS levels. At each level, you can reach a range of indices. The minimum jumps equals the number of levels you must expand.
Hint 2: Track current_end (rightmost index reachable with the current number of jumps) and farthest (rightmost reachable from any index visited so far). When i == current_end, increment jumps and set current_end = farthest.