Greedy Patterns: Interval Scheduling, Jump Game & Activity Selection
Greedy algorithms make the locally optimal choice at each step, hoping to reach a globally optimal solution. Master how to prove greedy correctness (exchange argument), the canonical greedy problems — interval scheduling, jump game, gas station, and task scheduler — and how to recognize when greedy fails and dynamic programming is needed instead.
The Greedy Insight: When Local Optimal = Global Optimal
A greedy algorithm works by making the best available choice at each step without reconsidering previous choices. This is fundamentally different from dynamic programming, which considers all subproblems. The critical question for any greedy problem is: does making the locally optimal choice at each step guarantee the globally optimal solution?
The exchange argument is how you prove greedy correctness: assume an optimal solution makes a different choice at some step. Show that you can "exchange" that choice for the greedy choice without making the solution worse. If you can always exchange, the greedy solution is at least as good as optimal — therefore it IS optimal.
Greedy fails when: making the locally optimal choice prevents you from seeing a globally better path. Example: in a graph with weighted edges, greedily picking the smallest edge at each step (Prim's) works for minimum spanning tree, but greedily picking the smallest edge toward the destination (naive Dijkstra without a priority queue) doesn't work for shortest path with non-uniform edge weights.
Signal words: "maximize the number of" (activities, tasks), "minimize the cost of" (connections, resources), "earliest deadline," "job scheduling," "can you reach the end?"
What Interviewers Evaluate
6/10: Recognizes greedy is applicable. Gets a correct solution after hints. Can't prove it.
8/10: Identifies the greedy choice and sorts correctly (sort by end time for interval scheduling, sort by deadline for earliest-deadline-first). Implements cleanly. Explains why greedy works for this specific problem.
10/10: Distinguishes greedy from DP: "This problem has the greedy choice property — making the local optimal choice never rules out a globally optimal solution. I can prove this with an exchange argument..." Identifies when greedy appears to work but doesn't (e.g., coin change with non-standard denominations). Connects greedy to real algorithms: Huffman coding, Prim's/Kruskal's, Dijkstra's.
Greedy Problem Categories
Interval Scheduling: sort by END time, greedily select
Select the maximum number of non-overlapping intervals. Greedy: sort intervals by end time. Always pick the interval that ends earliest (that doesn't overlap the last selected). Why? The interval ending earliest leaves the most time for future intervals. Proof: if an optimal solution picks interval A (ends later) instead of interval B (ends earlier), swapping B for A doesn't worsen the solution — B ends before A so B fits wherever A fits, and leaves MORE room. O(n log n) sort + O(n) scan.
Activity Selection: sort by deadline, earliest-deadline-first (EDF)
Minimize lateness (each job has deadline and duration; lateness = finish_time - deadline). Strategy: sort jobs by deadline, execute in that order. Proof: if two adjacent jobs are out of deadline order, swapping them reduces or maintains total lateness. The EDF schedule minimizes maximum lateness. Used in: real-time scheduling, CPU task queues.
Jump Game: backward greedy / forward reach tracking
Can you reach the end from position 0, where nums[i] is the max jump distance from position i? Forward approach: maintain max_reach = 0. For each position i: if i > max_reach, return False (can't reach i). Update max_reach = max(max_reach, i + nums[i]). If max_reach >= last_index, return True. Greedy insight: we never need to track which jump we take, only the farthest reachable position.
Gas Station: total surplus check
Can you complete a circular tour if station i provides gas[i] and costs cost[i]? Greedy: if total(gas) >= total(cost), a solution always exists (Proof: if total surplus is non-negative, there's always a starting point where you don't go negative). Find the start: reset accumulated surplus to 0 whenever it goes negative; the next station after the reset is the candidate start.
Task Scheduler: most-frequent-first greedy
Minimum time to execute all tasks with cooldown n between same-type tasks. Key insight: schedule the most frequent task first, then others, then idle if needed. Formula: (max_freq - 1) × (n + 1) + count_of_tasks_with_max_freq. This gives the minimum intervals needed. If total tasks > this formula, all tasks can be scheduled without idle time.
Interval Scheduling: Sort by End Time
Core Templates
Max Non-Overlapping Intervals (interval scheduling):
def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x: x[1]) # sort by END time
count = 0 # selected intervals
last_end = float('-inf')
for start, end in intervals:
if start >= last_end: # non-overlapping
count += 1
last_end = end
return len(intervals) - count # intervals to REMOVE
# O(n log n) sort + O(n) scan
Jump Game I (can you reach end?):
def canJump(nums: list[int]) -> bool:
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False # can't reach position i
max_reach = max(max_reach, i + jump)
return True
# O(n) time, O(1) space
Jump Game II (minimum jumps to reach end):
def jump(nums: list[int]) -> int:
jumps = current_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end: # we've exhausted the current jump
jumps += 1
current_end = farthest
return jumps
# O(n) time, O(1) space — greedy: jump to the farthest reachable point
Gas Station:
def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
total_surplus = current_surplus = start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total_surplus += diff
current_surplus += diff
if current_surplus < 0: # can't continue from this start
start = i + 1
current_surplus = 0
return start if total_surplus >= 0 else -1
# O(n) time, O(1) space
Greedy vs DP: When to Use Which
| Problem type | Use greedy when | Use DP when | Example |
|---|---|---|---|
| Interval scheduling | Maximize # of non-overlapping intervals | Maximize TOTAL VALUE of selected intervals (weighted) | Unweighted: greedy. Weighted job scheduling: DP |
| Coin change | Denominations are powers of each other (US coins) | Denominations are arbitrary (can't always pick largest) | US coins: greedy works. [1,3,4] denominations: greedy fails (4+1+1 vs 3+3) |
| Path problems | All positive weights, no cycles | Negative weights or cycles exist | Dijkstra (greedy). Bellman-Ford (DP) |
| Scheduling with cost | Minimize max lateness (EDF) | Minimize total weighted lateness | Single machine: EDF greedy. Weighted: DP/branch-bound |
| Subset selection | Greedy choice property provable | Overlapping subproblems, no greedy choice property | Fractional knapsack: greedy. 0/1 knapsack: DP |
When Greedy Fails
Coin change with non-standard denominations: Coins = [1, 3, 4], target = 6. Greedy picks 4 (largest ≤ 6), then 1, 1 → 3 coins. Optimal: 3 + 3 → 2 coins. Greedy fails because choosing the largest coin locally prevents finding the better 3+3 combination.
Weighted interval scheduling: You have jobs with values and time windows. Greedy "pick highest-value non-overlapping job" fails: you might skip two medium-value jobs that together outweigh the one high-value job. DP (sort by end time, for each job choose max of: skip it, or take it + best for jobs ending before it starts) solves this.
0/1 knapsack: Items have weight and value. Greedy "pick highest value/weight ratio" fails because items can't be fractionally taken. Fractional knapsack (items can be split) = greedy. 0/1 knapsack = DP.
How to test greedy in an interview: Try to construct a counterexample. If your greedy strategy is "pick the one with highest X," try: can two lower-X options ever beat one high-X option? If yes → not greedy, use DP. If no (provably, via exchange argument) → greedy is correct.
Interview Delivery Summary
Always state the greedy choice explicitly: "I'll sort by end time and greedily select intervals that don't overlap the last selected. The key insight is that choosing the interval that ends earliest maximizes remaining space for future selections."
Distinguish from DP: "If this were the weighted version — where each interval has a profit — greedy wouldn't work because we'd need to consider whether skipping a profitable late-ending interval is worth it. That would be DP."
State time complexity from the sort: "O(n log n) from sorting, O(n) for the greedy scan."