Greedy Algorithm Patterns: From Activity Selection to Huffman

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. When it works, greedy is beautiful: simple to implement, fast to run, and elegant to prove. But you must verify correctness; blindly applying greedy can give wrong answers.

When does greedy work?

Two conditions must hold:

1. Greedy choice property: A locally optimal choice is part of some globally optimal solution.
2. Optimal substructure: After making the greedy choice, the remaining problem is a smaller instance of the same problem.

Pattern 1: activity selection

Problem: Given n activities with start and finish times, select the maximum number of non-overlapping activities.

Greedy strategy: Always pick the activity that finishes earliest.

def activity_selection(activities):
    """
    Select maximum non-overlapping activities.
    Sort by finish time, greedily pick earliest-finishing.

    Time: O(n log n) for sort
    Space: O(1) extra
    """
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected


activities = [(1, 3), (2, 5), (3, 4), (0, 7), (5, 8), (6, 9), (8, 10)]
result = activity_selection(activities)
print(f"Selected {len(result)} activities: {result}")
# Selected 4 activities: [(1, 3), (3, 4), (5, 8), (8, 10)]

Proof by exchange argument

Let G = greedy solution and O = any optimal solution, both sorted by finish time.

Suppose they differ at position i. Greedy picks g_i (earliest finish), optimal picks o_i. Since greedy always picks earliest finish: g_i.end <= o_i.end.

Replace o_i with g_i in O. Since g_i ends no later, all subsequent activities in O remain compatible. The solution size does not decrease. Repeat until O matches G. Therefore |G| = |O|, and greedy is optimal.

Variations

def max_non_overlapping_intervals(intervals):
    """
    Minimum number of intervals to remove so the rest don't overlap.
    Equivalent to: total - max_non_overlapping.
    """
    intervals.sort(key=lambda x: x[1])
    count = 1
    end = intervals[0][1]

    for start, finish in intervals[1:]:
        if start >= end:
            count += 1
            end = finish

    return len(intervals) - count


intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
print(max_non_overlapping_intervals(intervals))  # 1 (remove [1,3])

Pattern 2: fractional knapsack

Problem: Given items with weights and values, and a knapsack capacity, maximize value. You can take fractions of items.

Greedy strategy: Sort by value-to-weight ratio, take as much as possible of the highest-ratio items.

def fractional_knapsack(items, capacity):
    """
    Fractional knapsack: take fractions of items.
    items: list of (value, weight) tuples

    Time: O(n log n)
    Space: O(1)
    """
    # Sort by value/weight ratio in decreasing order
    items.sort(key=lambda x: x[0] / x[1], reverse=True)

    total_value = 0.0
    remaining = capacity

    for value, weight in items:
        if remaining <= 0:
            break

        if weight <= remaining:
            # Take the whole item
            total_value += value
            remaining -= weight
        else:
            # Take a fraction
            fraction = remaining / weight
            total_value += value * fraction
            remaining = 0

    return total_value


items = [(60, 10), (100, 20), (120, 30)]
capacity = 50
print(f"Max value: {fractional_knapsack(items, capacity)}")
# Max value: 240.0
# Take all of item1 (60), all of item2 (100),
# 20/30 of item3 (80) = 240

Why greedy works: Since we can take fractions, there is never a reason to skip a higher-ratio item. Taking any fraction of the best-ratio item is at least as good as taking that fraction of a worse-ratio item.

Why greedy fails for 0/1 knapsack: You cannot take fractions. Picking a high-ratio item might prevent you from fitting two lower-ratio items that together give more value.

Pattern 3: Huffman coding

Problem: Given character frequencies, build a binary code where frequent characters get shorter codes. The code must be prefix-free (no code is a prefix of another).

Greedy strategy: Always merge the two least-frequent nodes.

import heapq

class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq


def huffman_coding(freq_map):
    """
    Build Huffman tree and return character codes.
    Time: O(n log n)
    Space: O(n)
    """
    # Create leaf nodes
    heap = [HuffmanNode(char, freq) for char, freq in freq_map.items()]
    heapq.heapify(heap)

    if len(heap) == 1:
        return {heap[0].char: "0"}

    # Build tree by merging two smallest
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        merged = HuffmanNode(
            freq=left.freq + right.freq,
            left=left,
            right=right
        )
        heapq.heappush(heap, merged)

    # Extract codes
    codes = {}

    def build_codes(node, code=""):
        if node is None:
            return
        if node.char is not None:
            codes[node.char] = code if code else "0"
            return
        build_codes(node.left, code + "0")
        build_codes(node.right, code + "1")

    build_codes(heap[0])
    return codes


def huffman_encode(text, codes):
    """Encode text using Huffman codes."""
    return "".join(codes[c] for c in text)


def huffman_decode(encoded, root):
    """Decode Huffman-encoded binary string."""
    result = []
    node = root
    for bit in encoded:
        node = node.left if bit == "0" else node.right
        if node.char is not None:
            result.append(node.char)
            node = root
    return "".join(result)


# Example
freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
codes = huffman_coding(freq)
print("Huffman Codes:")
total_bits = 0
for char, code in sorted(codes.items()):
    print(f"  '{char}' (freq={freq[char]}): {code}")
    total_bits += freq[char] * len(code)

print(f"\nTotal bits needed: {total_bits}")
print(f"Fixed-length would need: {sum(freq.values()) * 3} bits (3 bits each)")

Why greedy works: Merging the two smallest frequencies first ensures the least-frequent characters end up deepest in the tree (longest codes). Swapping a more-frequent character to a deeper level would increase the total cost.

Pattern 4: job scheduling with deadlines

Problem: Given n jobs with deadlines and profits, schedule jobs to maximize profit. Each job takes 1 unit of time, and you can do at most one job per time unit.

Greedy strategy: Sort by profit (descending), schedule each job as late as possible before its deadline.

def job_scheduling(jobs):
    """
    Schedule jobs to maximize profit.
    jobs: list of (job_id, deadline, profit)

    Time: O(n^2) with simple slot finding, O(n log n) with union-find
    Space: O(max_deadline)
    """
    # Sort by profit descending
    jobs.sort(key=lambda x: x[2], reverse=True)

    max_deadline = max(job[1] for job in jobs)
    slots = [None] * (max_deadline + 1)  # 1-indexed
    total_profit = 0
    scheduled = []

    for job_id, deadline, profit in jobs:
        # Find the latest available slot <= deadline
        for slot in range(deadline, 0, -1):
            if slots[slot] is None:
                slots[slot] = job_id
                total_profit += profit
                scheduled.append((job_id, slot, profit))
                break

    return total_profit, scheduled


jobs = [
    ('J1', 2, 100),
    ('J2', 1, 19),
    ('J3', 2, 27),
    ('J4', 1, 25),
    ('J5', 3, 15),
]

profit, schedule = job_scheduling(jobs)
print(f"Max profit: {profit}")
for job_id, slot, p in sorted(schedule, key=lambda x: x[1]):
    print(f"  Time {slot}: {job_id} (profit={p})")
# Max profit: 142
# Time 1: J3 (profit=27)
# Time 2: J1 (profit=100)
# Time 3: J5 (profit=15)

Pattern 5: minimum platforms

Problem: Given arrival and departure times of trains, find the minimum number of platforms needed so no train has to wait.

def min_platforms(arrivals, departures):
    """
    Minimum platforms needed at a station.
    Time: O(n log n)
    Space: O(1)
    """
    arrivals.sort()
    departures.sort()

    platforms_needed = 0
    max_platforms = 0
    i, j = 0, 0

    while i < len(arrivals):
        if arrivals[i] <= departures[j]:
            platforms_needed += 1
            max_platforms = max(max_platforms, platforms_needed)
            i += 1
        else:
            platforms_needed -= 1
            j += 1

    return max_platforms


arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
print(f"Minimum platforms: {min_platforms(arrivals, departures)}")
# Minimum platforms: 3

Alternative approach using events:

def min_platforms_events(arrivals, departures):
    """
    Event-based approach: +1 for arrival, -1 for departure.
    """
    events = []
    for a in arrivals:
        events.append((a, 1))   # arrival
    for d in departures:
        events.append((d + 1, -1))  # departure (after the time)

    events.sort()

    current = 0
    maximum = 0
    for _, delta in events:
        current += delta
        maximum = max(maximum, current)

    return maximum

Pattern 6: gas station (circular tour)

Problem: There are n gas stations in a circle. At station i you get gas[i] fuel and it costs cost[i] to reach station i+1. Find the starting station index, or -1 if no solution.

def can_complete_circuit(gas, cost):
    """
    Find starting station for circular tour.
    Time: O(n), Space: O(1)

    Key insight: if total gas >= total cost, a solution exists.
    Start from the station after the point where cumulative
    surplus is lowest.
    """
    if sum(gas) < sum(cost):
        return -1

    tank = 0
    start = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            # Cannot start from 'start' or any station
            # between start and i
            start = i + 1
            tank = 0

    return start


gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(f"Start at station: {can_complete_circuit(gas, cost)}")
# Start at station: 3

Why greedy works: If the total gas covers the total cost, a valid starting point must exist. Any time the tank goes negative, the current start and all stations between it and the negative point cannot be valid starts (they would also go negative at the same point or earlier).

Pattern 7: assign cookies

def find_content_children(greed, cookies):
    """
    Assign cookies to children. Each child has a greed factor.
    A cookie satisfies a child if cookie size >= greed.
    Maximize satisfied children.

    Time: O(n log n + m log m)
    Space: O(1)
    """
    greed.sort()
    cookies.sort()

    child = cookie = 0
    while child < len(greed) and cookie < len(cookies):
        if cookies[cookie] >= greed[child]:
            child += 1  # Child satisfied
        cookie += 1  # Try next cookie either way

    return child


print(find_content_children([1, 2, 3], [1, 1]))     # 1
print(find_content_children([1, 2], [1, 2, 3]))      # 2

Pattern 8: jump game II (minimum jumps)

def jump(nums):
    """
    Minimum jumps to reach the last index.
    Greedy: BFS-like level tracking.

    Time: O(n), Space: O(1)
    """
    jumps = 0
    current_end = 0    # Farthest index reachable with 'jumps' jumps
    farthest = 0       # Farthest index reachable with 'jumps + 1' jumps

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

            if current_end >= len(nums) - 1:
                break

    return jumps


print(jump([2, 3, 1, 1, 4]))  # 2 (0 -> 1 -> 4)
print(jump([2, 3, 0, 1, 4]))  # 2 (0 -> 1 -> 4)

Pattern 9: interval merging

def merge_intervals(intervals):
    """
    Merge overlapping intervals.
    Time: O(n log n), Space: O(n)
    """
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged


print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]

Proving greedy correctness checklist

1. State the greedy choice precisely.
2. Prove greedy choice property: Show that an optimal solution exists that includes the greedy choice (exchange argument).
3. Prove optimal substructure: Show the remaining problem after the greedy choice is a smaller instance of the same problem.
4. Test with counterexamples: Try edge cases and adversarial inputs before committing to the proof.

# Common counterexample patterns to test:
# 1. All same values
# 2. Already sorted / reverse sorted
# 3. Single element
# 4. Two elements
# 5. Worst case for greedy (if it fails, you know quickly)

Complexity table

Problem	Time	Space	Key Operation
Activity Selection	O(n log n)	O(1)	Sort by end time
Fractional Knapsack	O(n log n)	O(1)	Sort by value/weight
Huffman Coding	O(n log n)	O(n)	Min-heap merges
Job Scheduling	O(n^2)	O(n)	Sort by profit, find slot
Minimum Platforms	O(n log n)	O(1)	Sort arrivals + departures
Gas Station	O(n)	O(1)	Track cumulative surplus
Jump Game II	O(n)	O(1)	BFS-like level tracking
Merge Intervals	O(n log n)	O(n)	Sort by start

Practice problems

Problem	Difficulty	Pattern
Activity Selection	Easy	Sort by end
Assign Cookies (LC 455)	Easy	Sort both arrays
Jump Game (LC 55)	Medium	Farthest reachable
Jump Game II (LC 45)	Medium	BFS levels
Gas Station (LC 134)	Medium	Cumulative surplus
Non-overlapping Intervals (LC 435)	Medium	Activity selection
Merge Intervals (LC 56)	Medium	Sort + merge
Task Scheduler (LC 621)	Medium	Greedy + math
Minimum Platforms	Medium	Two-pointer on events
Huffman Coding	Medium	Min-heap
Job Scheduling with Deadlines	Medium	Sort by profit
Fractional Knapsack	Easy	Sort by ratio

Key takeaways

1. Greedy works when the locally optimal choice is also globally optimal (greedy choice property).
2. Always prove correctness with the exchange argument or counterexamples before implementing.
3. Common greedy strategies: sort by end time, sort by ratio, sort by profit, track running maximum/minimum.
4. If greedy fails (coin change with arbitrary denominations, 0/1 knapsack), switch to dynamic programming.
5. Greedy algorithms are typically O(n log n) due to sorting, with O(1) extra space.