Greedy Algorithms Cheat Sheet: Every Interview Pattern in One Place

You have an interview in two days. You could spend that time re-reading textbooks, or you could have one page that covers every greedy pattern, every gotcha, and every complexity. This is that page.

The real challenge isn't writing a greedy algorithm. It's knowing when greedy actually works and not reaching for DP when the greedy choice is sitting right there, waving at you.

The Two Properties Every Greedy Problem Has

Before you commit to greedy, confirm both. One is not enough. This is the part where most people skip the check and then spend 20 minutes debugging a solution that was never going to work.

Greedy choice property: A locally optimal choice at each step leads to a globally optimal solution. You never need to revisit a decision.

Optimal substructure: The optimal solution to the full problem contains optimal solutions to its subproblems. This is shared with dynamic programming, but greedy goes further by claiming the locally best choice is always part of the global best.

If you can construct a swap argument, you're safe. Assume some optimal solution exists, then show you can swap any non-greedy choice for the greedy one without making things worse. That mental test is faster in an interview than a full proof, and it actually works.

When optimal substructure holds but the greedy choice property doesn't, you need DP. The classic trap: coin change with denominations {1, 3, 4} and target 6. Greedy grabs 4+1+1 for 3 coins. DP quietly finds 3+3 for 2. Greedy thought it was so clever.

How to Recognize a Greedy Problem

Sorting by one attribute reduces the problem to a scan. Activity selection, fractional knapsack, two-city scheduling. If sorting unlocks the solution, you are almost certainly looking at a greedy problem.

"Minimum number of X to achieve Y." Minimum platforms, minimum arrows to burst balloons, minimum jumps. Greedy finds the minimum by being locally aggressive in a way that turns out to be globally correct.

Local decisions are irreversible and obviously safe. In the Jump Game, extending your reach as far as possible costs nothing. You never give up options. That irreversibility without cost is one of the clearest greedy signals there is.

A priority queue controls what gets picked next. Task scheduler, Huffman coding, Dijkstra, Prim's. When the right next choice is always the current best element in a heap, that's greedy with structure.

The problem involves intervals. Sort by end time, then scan. This single observation solves activity selection, meeting rooms, non-overlapping intervals, and a dozen variants. It's almost unfair how often it applies.

Greedy Algorithm Pattern Reference

Interval Scheduling (Sort by End Time)

Sort intervals by end time. Greedily select any interval that starts after the last selected one ends.

def activity_selection(intervals):
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Complexity: O(n log n) time, O(1) extra space.

Applies to: Activity Selection, Non-overlapping Intervals (LeetCode 435), Minimum Number of Arrows (452), Course Schedule with deadlines.

Sorting by end time works because an interval that ends earliest leaves the most room for future intervals. Any solution using a later-ending interval can swap in the earlier-ending one and do at least as well. That's your swap argument, done.

Interval Partitioning (Minimum Rooms)

Different from selection. Here you assign all intervals to as few "rooms" as possible. Everyone has to attend. Nobody gets cut.

import heapq

def min_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

Complexity: O(n log n) time, O(n) space.

Applies to: Meeting Rooms II (LeetCode 253), minimum platforms, car pooling.

The heap size at any point equals the current number of overlapping intervals. When a room's meeting ends before the next one starts, you reuse it. Otherwise you open a new one and update the count. Simple enough to explain in under 30 seconds, which is about as long as you have.

Jump Game Variants

Jump Game I (can you reach the end?)

def can_jump(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

Jump Game II (minimum jumps to reach end)

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

Complexity: O(n) time, O(1) space for both.

In Jump II, you never choose which cell to land on within a jump window. You track the farthest you could possibly reach and count how many times you exhaust a window. The implicit greedy is what makes it O(n) instead of a branching nightmare.

Gas Station

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank, start = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

Complexity: O(n) time, O(1) space.

Whenever the tank goes negative, the current starting point and everything before it is ruled out. The next candidate is the very next station. No need to restart the simulation from scratch. One pass and you're done.

Task Scheduler

from collections import Counter
import heapq

def least_interval(tasks, n):
    freq = Counter(tasks)
    heap = [-f for f in freq.values()]
    heapq.heapify(heap)
    time = 0
    while heap:
        cycle = []
        for _ in range(n + 1):
            if heap:
                cycle.append(heapq.heappop(heap))
        for f in cycle:
            if f + 1 < 0:
                heapq.heappush(heap, f + 1)
        time += n + 1 if heap else len(cycle)
    return time

Complexity: O(n log k) where k is the number of distinct tasks. O(k) space.

There's also a math formula: max(len(tasks), (max_freq - 1) * (n + 1) + count_of_max_freq_tasks). Know both. The heap version is easier to derive under pressure; the formula is easier to explain.

Fractional Knapsack

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total = 0
    for value, weight in items:
        if capacity <= 0:
            break
        take = min(weight, capacity)
        total += take * (value / weight)
        capacity -= take
    return total

Complexity: O(n log n) time, O(1) space.

Fractional knapsack is greedy. 0/1 knapsack is not. The distinction is whether you can take a fraction of an item. If you must take all or nothing, greedy falls apart and DP is waiting to save you.

Two-City Scheduling

def two_city_sched_cost(costs):
    costs.sort(key=lambda c: c[0] - c[1])
    n = len(costs) // 2
    return sum(c[0] for c in costs[:n]) + sum(c[1] for c in costs[n:])

Complexity: O(n log n) time, O(1) space.

Sort by cost_A - cost_B, the marginal cost of choosing city A over city B. People with the most negative difference go to A. You want the n smallest marginal costs, so sort, split down the middle, done. Four lines of code, five seconds to explain. This is greedy at its most satisfying.

Complexity Table

Pattern	Time	Space	Key Operation
Activity selection	O(n log n)	O(1)	Sort by end time
Meeting rooms II	O(n log n)	O(n)	Sort + min-heap
Jump Game I	O(n)	O(1)	Greedy reach
Jump Game II	O(n)	O(1)	Window + reach
Gas Station	O(n)	O(1)	Running sum
Task Scheduler	O(n log k)	O(k)	Max-heap
Fractional knapsack	O(n log n)	O(1)	Sort by ratio
Two-city scheduling	O(n log n)	O(1)	Sort by diff
Dijkstra	O((V+E) log V)	O(V)	Priority queue
Prim's MST	O((V+E) log V)	O(V)	Priority queue
Kruskal's MST	O(E log E)	O(V)	Sort + union-find
Huffman coding	O(n log n)	O(n)	Min-heap merging

When Greedy Fails (Memorize These)

These are the counterexamples interviewers love to probe with. "What if I changed the problem slightly?" usually means one of these.

Coin change with arbitrary denominations. Coins {1, 3, 4}, target 6: greedy confidently grabs 4+1+1 for 3 coins. DP finds 3+3 for 2. Greedy works only for canonical systems like US coins because someone designed those denominations to be greedy-friendly. Most denominations are not.

0/1 Knapsack. You cannot take fractions, so the best value-per-weight item might not fit. The greedy choice property breaks immediately. This is why fractional knapsack is in every algorithms course as a greedy example and 0/1 knapsack is in every DP section.

Longest path in a general graph. Shortest path is greedy (Dijkstra). Longest path is NP-hard. The swap argument that works for shortest paths completely breaks for longest paths. Same structure, opposite answer.

Negative edge weights. Dijkstra greedily marks nodes as finalized. A negative edge could later improve a finalized node's distance, violating the entire invariant. Use Bellman-Ford. Dijkstra on negative weights is a confident wrong answer that will cost you the round.

Scheduling with deadlines and non-uniform profits. Earliest Deadline First minimizes lateness beautifully. But when jobs have unequal profits and you must choose which to reject, the local reasoning stops holding. A job with a huge profit and a late deadline might be worth keeping even if it causes smaller jobs to miss.

The test to run before committing to greedy: can you prove a swap argument? If swapping any non-greedy choice for the greedy one never makes things worse, you're safe. If you can construct a single counterexample where the swap hurts, stop and reach for DP. This mental check takes under a minute and will save you from the most common interview mistake in this category.

Picking the Right Sort Key

The trickiest part of a greedy problem is usually figuring out what to sort by. Get this wrong and the rest of the code is fast but incorrect.

Sort by the costly end of a constraint. Intervals: sort by end time, not start, because late finishers block future selections. Deadlines: sort by deadline. The "costly end" framing almost always points you at the right attribute.

Sort by a ratio when you're balancing two quantities. Fractional knapsack: value/weight. Two-city: cost_A minus cost_B. When two quantities trade off against each other, the ratio between them is usually the sort key.

Sort by the opposite of what you want to maximize. If you want to maximize a count, sort by what terminates a streak soonest. Picking the least greedy option first leaves the most room for future picks. This is counterintuitive, which is why it trips people up, and why you want to have seen it before the interview.

Prep With the Patterns, Not Just the Problems

Recognizing which greedy pattern applies is the interview skill. A problem that looks like it needs DP might have the greedy choice property hiding inside it. Sorting might be the unlock. The swap argument might be obvious once you see it, but only if you've trained yourself to look.

SpaceComplexity runs voice-based mock interviews where you have to spot and justify the approach out loud, the same way you would with a real interviewer. You don't get to silently Google "greedy vs DP" and pretend you knew. Rubric-based feedback tells you whether your problem-solving reasoning was sound, not just whether your code compiled.

For more on when greedy works versus when DP is the right call, see Greedy vs Dynamic Programming and The Greedy Choice Property. If you want to see the patterns where greedy is the wrong instinct, Greedy Algorithm Mistakes covers the four that show up most often.

And if you want the complete pattern library alongside this one, DSA Patterns Cheat Sheet is the broader reference.