Greedy Algorithms — Deep Dive

Proving greedy correctness

A greedy algorithm is only useful if it produces optimal results. Two proof techniques establish correctness:

Exchange argument

Show that any optimal solution can be transformed into the greedy solution without worsening it.

Example: Activity selection proof.

Claim: Always selecting the activity with the earliest finish time gives the maximum number of non-overlapping activities.

Proof sketch: Let OPT be an optimal solution and G be the greedy solution. If OPT’s first activity differs from G’s first activity, we can swap OPT’s first activity for G’s first activity (which finishes no later), and OPT remains valid with the same number of activities. Repeating this argument for each position shows |G| ≥ |OPT|. Since OPT is optimal, |G| = |OPT|.

Greedy stays ahead

Show that at every step, the greedy solution is at least as good as any other solution at that step.

Example: Fractional knapsack.

At each step, greedy picks the item with the highest value/weight ratio. After adding k items, greedy has extracted the maximum possible value from those k selections. No alternative selection of k items could extract more value.

Huffman coding

Huffman coding is a greedy algorithm for optimal prefix-free encoding. It assigns shorter codes to more frequent symbols, minimizing total encoded length.

import heapq
from collections import Counter

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 build_huffman_tree(text):
    freq = Counter(text)
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq.items()]
    heapq.heapify(heap)

    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)

    return heap[0]

def build_codes(node, prefix="", codes=None):
    if codes is None:
        codes = {}
    if node.char is not None:
        codes[node.char] = prefix or "0"  # single char edge case
        return codes
    build_codes(node.left, prefix + "0", codes)
    build_codes(node.right, prefix + "1", codes)
    return codes

def huffman_encode(text):
    tree = build_huffman_tree(text)
    codes = build_codes(tree)
    encoded = "".join(codes[c] for c in text)
    return encoded, codes

text = "abracadabra"
encoded, codes = huffman_encode(text)
print(f"Original: {len(text) * 8} bits")
print(f"Encoded: {len(encoded)} bits")
print(f"Codes: {codes}")
# Typical output: a→0, b→10, r→110, c→1110, d→1111
# 5 a's get 1-bit codes, saving significant space

Time complexity: O(n log n) where n is the number of distinct symbols (heap operations). Why greedy works: Combining the two lowest-frequency nodes first guarantees they get the longest codes, minimizing weighted path length.

Dijkstra’s shortest path

Dijkstra’s algorithm is greedy: always expand the nearest unvisited node.

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    distances = {start: 0}
    heap = [(0, start)]
    visited = set()

    while heap:
        dist, node = heapq.heappop(heap)

        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                new_dist = dist + weight
                if new_dist < distances.get(neighbor, float('inf')):
                    distances[neighbor] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor))

    return distances

# Build graph as adjacency list
graph = defaultdict(list)
edges = [('A', 'B', 1), ('A', 'C', 4), ('B', 'C', 2), ('B', 'D', 5), ('C', 'D', 1)]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))

print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Time complexity: O((V + E) log V) with a binary heap. Why greedy works: With non-negative edge weights, the shortest path to the nearest unvisited node cannot be improved by going through a more distant node first. Limitation: Fails with negative edge weights — use Bellman-Ford instead.

Interval scheduling variations

Weighted interval scheduling

When activities have weights (profits) and you want maximum total weight, greedy no longer works. This requires dynamic programming with binary search:

import bisect

def weighted_interval_scheduling(intervals):
    # intervals: list of (start, end, weight)
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    ends = [iv[1] for iv in intervals]

    # p[i] = index of latest interval that finishes before interval i starts
    def find_prev(i):
        idx = bisect.bisect_right(ends, intervals[i][0]) - 1
        return idx

    # dp[i] = max weight using intervals 0..i
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        weight = intervals[i-1][2]
        prev = find_prev(i - 1)
        dp[i] = max(dp[i-1], weight + dp[prev + 1])

    return dp[n]

intervals = [(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4), (5, 8, 11), (7, 9, 2)]
print(weighted_interval_scheduling(intervals))  # 17

Minimum platforms (meeting rooms)

Find the minimum number of platforms/rooms needed for all overlapping events:

def min_platforms(arrivals, departures):
    events = []
    for a in arrivals:
        events.append((a, 1))   # arrival: +1 platform
    for d in departures:
        events.append((d, -1))  # departure: -1 platform

    events.sort()
    current = 0
    max_platforms = 0
    for _, delta in events:
        current += delta
        max_platforms = max(max_platforms, current)

    return max_platforms

arrivals = [9.00, 9.40, 9.50, 11.00, 15.00, 18.00]
departures = [9.10, 12.00, 11.20, 11.30, 19.00, 20.00]
print(min_platforms(arrivals, departures))  # 3

Why greedy works: The sweep line processes events in chronological order, and the maximum overlap at any point is the exact number of platforms needed.

Greedy on strings

Remove K digits for smallest number

Given a string of digits, remove k digits to make the smallest possible number:

def remove_k_digits(num, k):
    stack = []
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # If k remaining, remove from end (digits are ascending)
    stack = stack[:len(stack) - k] if k > 0 else stack

    # Remove leading zeros
    result = "".join(stack).lstrip("0")
    return result or "0"

print(remove_k_digits("1432219", 3))  # "1219"
print(remove_k_digits("10200", 1))    # "200"

Greedy insight: Whenever a digit is followed by a smaller digit, removing the larger digit produces a smaller number. The monotonic stack enforces this greedily.

Task scheduling with cooldown

Schedule tasks with a mandatory cooldown period between same tasks to minimize total time:

from collections import Counter

def least_interval(tasks, cooldown):
    counts = Counter(tasks)
    max_freq = max(counts.values())
    max_freq_count = sum(1 for c in counts.values() if c == max_freq)

    # Greedy formula: arrange most frequent tasks first
    # (max_freq - 1) groups of (cooldown + 1) slots + max_freq_count final tasks
    min_length = (max_freq - 1) * (cooldown + 1) + max_freq_count

    # Cannot be shorter than total tasks
    return max(min_length, len(tasks))

print(least_interval(["A","A","A","B","B","B"], 2))  # 8
# A B _ A B _ A B

Why greedy works: The most frequent task determines the structure. Filling gaps between its occurrences with other tasks is optimal because it minimizes idle slots.

Anti-patterns: when greedy looks right but is wrong

0/1 Knapsack counterexample

# Items: (weight, value)
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50

# Greedy by value/weight: picks item 0 (6.0) then item 1 (5.0) → total 160
# Optimal: items 1 + 2 → weight 50, value 220

# Greedy fails because you cannot take fractions

Change-making counterexample

# Denominations: [1, 15, 25]
# Target: 30

# Greedy: 25 + 1×5 = 6 coins
# Optimal: 15 + 15 = 2 coins

When greedy gives approximations

For NP-hard problems where exact solutions are too slow, greedy algorithms often provide good approximations with provable bounds:

• Set cover: Greedy achieves O(log n) approximation ratio
• Vertex cover: 2-approximation via maximal matching
• TSP (metric): Nearest-neighbor heuristic is within factor 2 of optimal

def greedy_set_cover(universe, subsets):
    covered = set()
    selected = []

    while covered != universe:
        # Greedy: pick the subset that covers the most uncovered elements
        best = max(subsets, key=lambda s: len(s - covered))
        selected.append(best)
        covered |= best

    return selected

universe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
subsets = [{1, 2, 3}, {4, 5, 6}, {7, 8, 9, 10}, {1, 4, 7}, {2, 5, 8}, {3, 6, 9, 10}]
print(greedy_set_cover(universe, subsets))

One thing to remember: The power of greedy algorithms lies in their simplicity and efficiency, but that power only works when you can prove the greedy choice property holds. Before implementing, always ask: “Can I construct a counterexample where greedy fails?” If you can, switch to dynamic programming. If you cannot, and you can sketch an exchange argument, greedy is the right choice.