What Makes a Problem Greedy-Solvable?
A greedy algorithm makes the locally optimal choice at each step and never backtracks. Two conditions must hold: (1) Greedy choice property: a globally optimal solution can be reached by making locally optimal choices. (2) Optimal substructure: an optimal solution to the problem contains optimal solutions to its subproblems. Recognition: “at each step, take the best available option” without needing to undo that choice later. If you find yourself needing to un-make a choice, the problem likely requires DP or backtracking instead.
Interval Scheduling (Activity Selection)
Given intervals [start, end], find the maximum number of non-overlapping intervals. Greedy: sort by end time, greedily pick each interval that starts after the previous one ends.
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # take this interval
else:
count += 1 # remove this interval (overlaps)
return count
Proof: at each step, the interval with the earliest end time leaves the most room for future intervals — any other choice can only do worse or equal.
Jump Game (LC 55, 45)
# LC 55: Can you reach the end?
def canJump(nums):
max_reach = 0
for i, n in enumerate(nums):
if i > max_reach: return False
max_reach = max(max_reach, i + n)
return True
# LC 45: Minimum jumps to reach end
def jump(nums):
jumps = cur_end = cur_far = 0
for i in range(len(nums) - 1):
cur_far = max(cur_far, i + nums[i])
if i == cur_end: # must jump
jumps += 1
cur_end = cur_far # extend reach
return jumps
Gas Station (LC 134)
Greedy: if total gas >= total cost, a solution exists. Start from index 0; track running surplus. When surplus goes negative, reset the starting point to the next station.
def canCompleteCircuit(gas, cost):
total = tank = start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank = 0 else -1
Task Scheduler (LC 621)
Minimum time to execute all tasks with cooldown n between same tasks. Greedy: schedule the most frequent task first to fill cooldown gaps. Formula: result = max((max_count – 1) * (n + 1) + num_tasks_with_max_count, len(tasks)).
from collections import Counter
def leastInterval(tasks, n):
counts = Counter(tasks)
max_count = max(counts.values())
num_max = sum(1 for v in counts.values() if v == max_count)
return max((max_count - 1) * (n + 1) + num_max, len(tasks))
Candy Distribution (LC 135)
Each child must have at least 1 candy. Children with higher ratings than neighbors get more candies. Two-pass greedy: left-to-right pass ensures left-to-right constraints; right-to-left pass ensures right-to-left constraints. Take the max at each position.
def candy(ratings):
n = len(ratings)
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)
Greedy vs DP Decision
- Use greedy: single pass or two-pass suffices, no need to revisit choices, exchange argument provably holds (choosing differently leads to a worse or equal result)
- Use DP: optimal choice at step i depends on choices made at step i+1 or later, or greedy produces wrong answers on counterexamples
- Test greedy on edge cases before committing — greedy is often wrong for knapsack-style problems (fractional knapsack: greedy OK; 0/1 knapsack: greedy wrong)
Huffman Coding Pattern
Build an optimal prefix-free encoding using a min-heap. Always merge the two lowest-frequency nodes. Produces the minimum total encoding length. Pattern applies to any “merge smallest cost first” problem: connecting ropes (minimize total merge cost), hospital staffing (assign shifts to minimize overtime).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you identify if a problem can be solved greedily?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two conditions must hold: (1) Greedy choice property — making the locally optimal choice at each step leads to a globally optimal solution. This must be provable; intuition alone is not enough. (2) Optimal substructure — the problem can be broken down into subproblems, and optimal solutions to subproblems yield an optimal solution overall (same as DP). The key test: can you prove that choosing differently leads to a result that is no better? This is the exchange argument — assume there is an optimal solution that differs from your greedy choice at step k. Show you can swap the greedy choice in without making the solution worse. Common greedy patterns: sort by a key then make sequential choices (interval scheduling: sort by end time), track a running extremum (jump game, gas station), use a priority queue to always process the smallest/largest element next (Huffman coding, Dijkstra).”}},{“@type”:”Question”,”name”:”How does interval scheduling (activity selection / non-overlapping intervals) work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Problem: given intervals [start, end], find the maximum number of non-overlapping intervals (equivalently, the minimum number to remove). Greedy: sort intervals by end time. Iterate: maintain prev_end. If the current interval starts >= prev_end, it does not overlap — take it and update prev_end. If it overlaps, remove it (increment removal count). Proof (exchange argument): suppose we choose interval A (with earlier end) over interval B (with later end) at some step. We can swap B for A in any solution: A ends earlier, so it cannot cause more future conflicts than B. Therefore sorting by end time and greedily selecting non-overlapping intervals is optimal. Time O(n log n). LC 435 (Minimum Number to Remove), LC 452 (Minimum Arrows to Burst Balloons), LC 646 (Maximum Length of Pair Chain) all follow this pattern.”}},{“@type”:”Question”,”name”:”How do you solve the Jump Game (LC 55 and LC 45) greedily?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 55 (can you reach the end?): maintain max_reach = the farthest index reachable so far. At each index i: if i > max_reach, it is unreachable — return False. Otherwise, update max_reach = max(max_reach, i + nums[i]). If you never get stuck, return True. Time O(n), space O(1). LC 45 (minimum jumps): maintain cur_end = the boundary of the current jump, cur_far = farthest reachable from any index in [0, cur_end]. When i reaches cur_end, you must make a jump — increment jump count, set cur_end = cur_far (extend to the farthest reachable). Iterate until i = n-1. Greedy correctness: at each jump, we always extend as far as possible, which minimizes the number of subsequent jumps needed.”}},{“@type”:”Question”,”name”:”When does greedy fail and dynamic programming is required instead?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Greedy fails when the locally optimal choice at step k depends on future choices, or when a greedy counterexample exists. Classic failures: (1) 0/1 Knapsack: greedy by value/weight ratio fails for integer items. Example: items [(6,4), (5,3), (5,3)], capacity 6. Greedy (best ratio) picks item 1 for value 6. DP picks items 2+3 for value 10. (2) Coin change (non-standard denominations): greedy gives the wrong answer for coins [1, 3, 4] and target 6. Greedy picks 4+1+1=3 coins; DP finds 3+3=2 coins. (3) Matrix chain multiplication: greedy fails; DP required. Test for greediness: try to construct a counterexample with small inputs. If greedy produces a different answer than the brute-force optimum on any example, use DP.”}},{“@type”:”Question”,”name”:”How does the task scheduler problem (LC 621) use greedy?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Given tasks with a cooldown n (same task cannot run within n steps of the previous execution), find minimum time to execute all tasks. Key insight: the bottleneck is the most frequent task — we must schedule it with idle slots between repetitions to satisfy the cooldown. Formula: result = max((max_count – 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Derivation: the most frequent task (count = max_count) creates max_count – 1 gaps of size n. Each gap can be filled with other tasks. num_tasks_with_max_count accounts for all tasks with the maximum frequency sharing the last slot. The max with total_tasks handles the case where there are enough diverse tasks to fill all cooldown gaps — no idle time needed. Greedy implementation: use a max-heap of frequencies, always schedule the most frequent remaining task, using a cooldown queue to track when each type becomes available.”}}]}
Google coding interviews test greedy algorithm patterns. See common questions for Google interview: greedy algorithm problems.
Meta coding interviews cover greedy and interval scheduling patterns. Review problems for Meta interview: greedy algorithm and interval problems.
Amazon coding interviews test greedy algorithms and scheduling. See patterns for Amazon interview: greedy algorithm and scheduling problems.