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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you solve the interval scheduling maximization problem?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Sort intervals by end time (not start time, not duration). Greedily select each interval whose start time is >= the end time of the last selected interval. This gives the maximum number of non-overlapping intervals in O(N log N). Why sort by end time? An interval ending earlier leaves the most room for future intervals. Sorting by start time fails: a long interval starting earliest blocks many shorter intervals. Sorting by duration fails: a short interval might overlap two others that together cover more time. The exchange argument: if the optimal solution uses interval B instead of interval A (A ends first), replacing B with A doesn't worsen the solution — A fits everywhere B fits, and potentially allows more intervals after it.” }
},
{
“@type”: “Question”,
“name”: “How do you solve the Jump Game problem greedily?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Track max_reach = the farthest index reachable from any position visited so far. Iterate left to right. At each index i: if i > max_reach, return False (stuck). Otherwise, update max_reach = max(max_reach, i + nums[i]). If max_reach >= last_index after any iteration, return True. This is O(N) time, O(1) space. For Jump Game II (minimum jumps): track current_end (end of current jump range) and farthest (best reach from within current range). When i reaches current_end, increment jump count and set current_end = farthest. This greedily picks the jump that extends reach furthest without explicitly backtracking.” }
},
{
“@type”: “Question”,
“name”: “How do you solve the Task Scheduler problem?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Find the most frequent task (max_freq). The minimum intervals needed is max((max_freq – 1) * (n + 1) + count_of_tasks_with_max_freq, total_tasks). Intuition: arrange tasks in a table with (n+1) columns. Fill max_freq rows with the most frequent task in the first column. Fill remaining columns with other tasks. The table has (max_freq-1) * (n+1) + last_row_tasks slots. If there are more tasks than fit, they eliminate idle slots and the answer is just total_tasks. This is O(N) time using just the max frequency count, or O(N log N) if you simulate with a max-heap. The formula is correct for all cases — verify with examples: tasks=[A,A,A,B,B,B], n=2 → (3-1)*(2+1)+2 = 8.” }
}
]
}