What Are Greedy Algorithms?
A greedy algorithm makes the locally optimal choice at each step, never backtracking, hoping that local optima lead to a global optimum. Unlike dynamic programming (which explores all subproblems), greedy algorithms are fast — typically O(N log N) or O(N) — but they only work when a greedy choice property holds: the locally optimal choice is always part of some globally optimal solution.
Proving greedy correctness requires either an “exchange argument” (show that swapping a non-greedy choice for the greedy choice never worsens the result) or showing the problem has optimal substructure with the greedy property. For interviews, knowing which problems fit greedy patterns is more important than formal proofs.
Pattern 1: Interval Scheduling
Classic problem: given a list of intervals, select the maximum number of non-overlapping intervals.
Greedy strategy: sort by end time. Greedily select each interval whose start is ≥ the end of the last selected interval.
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end
count, last_end = 0, float('-inf')
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
Why sort by end time? An interval ending earlier leaves more room for future intervals. Sorting by start time or duration doesn’t work — counterexamples exist for both.
Variation — Meeting Rooms II: minimum number of rooms to schedule all meetings. Use a min-heap of end times. Sort by start. For each meeting, if the earliest-ending room is free (heap.peek() ≤ current start), reuse it; otherwise, add a room. Answer: heap size at the end.
Pattern 2: Activity Scheduling with Deadlines
Given tasks with profits and deadlines, schedule tasks to maximize profit (each task takes 1 unit of time).
Greedy strategy: sort tasks by profit descending. For each task, schedule it as late as possible within its deadline (use a boolean array of time slots). A Union-Find structure optimizes finding the latest free slot to O(α(N)).
Pattern 3: Jump Game
Given an array where nums[i] is max jump length from position i, can you reach the last index?
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + jump)
return True
Track the farthest reachable index. If you’re ever at a position beyond max_reach, you’re stuck. For “minimum jumps to reach end” (Jump Game II): greedily take the jump that extends your reach the furthest at each step. O(N) time.
Pattern 4: Gas Station (Circular Tour)
N gas stations in a circle. gas[i] = gas available, cost[i] = gas needed to reach next station. Find starting station to complete the circuit, or return -1.
Key insight: if total_gas ≥ total_cost, a solution always exists. Find it by tracking running tank: whenever it goes negative, reset to 0 and set next station as new candidate start.
def can_complete_circuit(gas, cost):
total, tank, start = 0, 0, 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank = 0 else -1
Pattern 5: Task Scheduler
Given tasks with a cooldown n (same task can’t run within n slots of each other), find minimum intervals to execute all tasks.
Greedy strategy: always execute the most frequent remaining task. Fill idle slots with next most frequent. The minimum time is max(len(tasks), (max_freq – 1) * (n + 1) + count_of_max_freq_tasks).
The formula captures two cases: if tasks fill all slots without idle time, it’s just len(tasks); otherwise, the bottleneck is the most frequent task creating idle slots.
Pattern 6: Fractional Knapsack
Items with weights and values, maximize value with weight capacity W. Unlike 0/1 knapsack (requires DP), fractional knapsack is greedily solvable: sort by value/weight ratio, take items greedily (fractionally if needed).
Pattern 7: Huffman Encoding
Build an optimal prefix code: assign shorter codes to more frequent characters. Greedy: repeatedly merge the two lowest-frequency nodes using a min-heap. This builds the Huffman tree bottom-up. Result: provably optimal prefix-free code (no codeword is a prefix of another).
Recognizing Greedy Problems
- “Minimum number of X to cover Y”: interval covering, minimum coins/stamps
- “Maximum number of non-overlapping”: interval scheduling
- “Reach the end / complete the circuit”: jump game, gas station
- “Assign tasks to minimize total cost”: activity scheduling, Huffman
- Locally obvious choice: if there’s a clear “best” pick at each step, try greedy first
When Greedy Fails — Use DP Instead
- 0/1 Knapsack: can’t take fractions — greedy by ratio fails on integer-only items
- Coin change (arbitrary denominations): greedy fails for [1,3,4] coins with target 6 (greedy picks 4+1+1=3 coins; optimal is 3+3=2 coins)
- Longest common subsequence: locally optimal character matches don’t guarantee globally longest subsequence
Interview Tips
- When you propose a greedy solution, expect the interviewer to ask “prove it’s correct” or “give a counterexample.” Have the exchange argument ready.
- For interval problems, always ask: sort by start, end, or length? Drawing examples on the whiteboard makes this intuitive.
- Greedy + heap is a powerful combination: task scheduler, meeting rooms II, K closest points — heap lets you greedily pick the best item in O(log N).
- Contrast with DP: “greedy makes one choice; DP evaluates all choices.” If your greedy fails a small example, switch to DP.
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
Asked at: Airbnb Interview Guide