Greedy Algorithm Interview Patterns
Greedy algorithms make the locally optimal choice at each step, hoping to find a global optimum. They are simpler and faster than dynamic programming (usually O(n log n) due to sorting), but only work when the problem has the greedy choice property — a local optimum leads to a global optimum.
When Greedy Works
Greedy applies when:
- Optimal substructure — optimal solution contains optimal solutions to sub-problems
- Greedy choice property — a locally optimal choice never needs to be revised
Proof technique: “exchange argument” — assume the optimal solution differs from greedy at step k, then show swapping greedy’s choice in doesn’t worsen the result.
Pattern 1: Interval Scheduling
Select maximum number of non-overlapping intervals. Sort by end time, greedily pick intervals that start after the last selected one ends.
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
# Minimum number of meeting rooms (sort by start, use min-heap on end times)
import heapq
def min_meeting_rooms(intervals):
intervals.sort()
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end)
else:
heapq.heappush(heap, end)
return len(heap)
Pattern 2: Jump Game
Track the maximum reachable index as you scan left to right:
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False # can't reach this position
max_reach = max(max_reach, i + jump)
return True
def jump_game_ii(nums):
# Minimum jumps to reach end
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 here
jumps += 1
cur_end = cur_far # extend reach
return jumps
Pattern 3: Gas Station
If total gas >= total cost, a solution always exists. Start from where tank went negative:
def can_complete_circuit(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
Pattern 4: Task Scheduler
Always run the most frequent remaining task, or idle if cooldown prevents it:
from collections import Counter
import heapq
from collections import deque
def least_interval(tasks, n):
freq = Counter(tasks)
heap = [-f for f in freq.values()]
heapq.heapify(heap)
time = 0
cooldown = deque() # (available_time, neg_count)
while heap or cooldown:
time += 1
if heap:
cnt = 1 + heapq.heappop(heap) # decrement count
if cnt:
cooldown.append((time + n, cnt))
if cooldown and cooldown[0][0] == time:
heapq.heappush(heap, cooldown.popleft()[1])
return time
Pattern 5: Minimum Cost Greedy Problems
# Assign cookies: give smallest sufficient cookie to smallest child
def find_content_children(g, s):
g.sort(); s.sort()
child = cookie = 0
while child < len(g) and cookie = g[child]:
child += 1
cookie += 1
return child
# Boats to save people: two-pointer greedy
def num_rescue_boats(people, limit):
people.sort()
lo, hi = 0, len(people) - 1
boats = 0
while lo <= hi:
if people[lo] + people[hi] <= limit:
lo += 1
hi -= 1
boats += 1
return boats
Classic Greedy Interview Problems
| Problem | Greedy Strategy | Key Sort |
|---|---|---|
| Activity Selection / Non-overlapping Intervals | Pick earliest end time | By end time |
| Jump Game I & II | Track max reachable index | None |
| Gas Station | Reset start after negative tank | None |
| Task Scheduler | Most frequent task first | By frequency |
| Huffman Coding | Merge two smallest freq nodes | Min-heap |
| Fractional Knapsack | Highest value/weight ratio first | By ratio |
| Minimum Number of Arrows | Sort balloons by end, shoot at end | By end point |
| Partition Labels | Extend window to last occurrence | None |
Greedy vs DP Decision Framework
- Greedy: can prove local choice is always safe; O(n log n) typical
- DP: overlapping sub-problems; local choice depends on future decisions; O(n²) typical
- Rule of thumb: try greedy first (simpler), justify with exchange argument, fall back to DP if justification fails
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you prove a greedy algorithm is correct?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use the exchange argument: assume the optimal solution differs from greedy at the first disagreement point. Show that swapping in the greedy choice produces a solution no worse than the optimal. If you can always make this swap without worsening the result, the greedy algorithm is proven correct. For interval scheduling, this means showing that choosing the earliest end time never blocks more future intervals than any other choice.” }
},
{
“@type”: “Question”,
“name”: “What is the greedy approach to the interval scheduling problem?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Sort intervals by end time. Greedily select each interval that starts at or after the last selected interval ends. This maximizes the count of non-overlapping intervals. The key insight: finishing earlier always leaves more room for future intervals, so the earliest-ending interval is always a safe first choice.” }
},
{
“@type”: “Question”,
“name”: “How does greedy work for the Jump Game II (minimum jumps)?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Scan left to right maintaining two pointers: cur_end (boundary of current jump) and cur_far (farthest reachable position seen so far). When you reach cur_end, you must make a jump—increment jump count and set cur_end = cur_far. This implicitly explores all positions within reach before committing to a jump, achieving O(n) time without backtracking.” }
}
]
}