Greedy
Algorithms

What is a greedy algorithm?

A greedy algorithm builds a solution piece by piece, always choosing the locally optimal option at each step, hoping that local choices lead to a globally optimal solution.

• At each decision point, pick the choice that looks best right now
• Never reconsider previous choices — no backtracking
• Hope that local optimality leads to global optimality
• Much simpler and faster than exhaustive search or DP

The greedy template

GREEDY-SOLVE(problem):
    solution = empty
    while problem is not solved:
        candidate = SELECT best remaining option
        if candidate is FEASIBLE:
            solution = solution + candidate
    return solution

Proof strategy (exchange argument)

Problem

Given n activities with start and finish times (s_i, f_i), select the maximum number of non-overlapping activities.

Correctness proof sketch

1. Sort activities by finish time: f_1 <= f_2 <= ... <= f_n
2. Activity 1 (earliest finish) is in some OPT — if not, swap the first activity in OPT with activity 1; it finishes no later, so no new conflicts
3. After selecting activity 1, the remaining problem is the same type
4. By induction, the greedy algorithm is optimal

Implementation

def activity_selection(activities):
    # Sort by finish time
    activities.sort(key=lambda x: x[1])
    selected = [activities[0]]
    last_finish = activities[0][1]

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

    return selected

# Example
acts = [(0,6),(1,4),(3,5),(5,7),
        (3,9),(5,9),(6,10),(8,11)]
print(activity_selection(acts))
# [(1,4), (5,7), (8,11)]

Problem

Given characters with known frequencies, assign variable-length binary codes to minimise total encoded length.

• Frequent characters get short codes
• Rare characters get long codes
• Must be a prefix-free code — no code is a prefix of another — for unambiguous decoding

Example

Algorithm

1. Create a leaf node for each character with its frequency
2. Insert all nodes into a min-priority queue
3. While the queue has more than one node:
   • Extract the two nodes with lowest frequency
   • Create a new internal node with these as children; frequency = sum
   • Insert the new node back into the queue
4. The remaining node is the root of the Huffman tree

Implementation

import heapq

def huffman(freq):
    heap = [(f, i, char)
            for i, (char, f)
            in enumerate(freq.items())]
    heapq.heapify(heap)
    counter = len(heap)

    while len(heap) > 1:
        f1, _, left  = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        merged = (left, right)
        heapq.heappush(
            heap,
            (f1 + f2, counter, merged)
        )
        counter += 1

    return heap[0][2]  # root of tree

freq = {'a':45, 'b':13, 'c':12,
        'd':16, 'e':9,  'f':5}
tree = huffman(freq)

Problem

Given n items with weight w_i and value v_i, and a knapsack of capacity W, maximise total value. Fractions of items are allowed.

Greedy strategy

1. Compute value-to-weight ratio v_i / w_i
2. Sort items by ratio in decreasing order
3. Take whole items if they fit; otherwise take the fraction that fills the remaining capacity

Example

Capacity W = 50:

Total: 60 + 100 + (20/30)×120 = 240

Problem

Given n jobs with deadline d_i and profit p_i, each taking one unit of time, schedule on a single machine to maximise total profit. A job earns its profit only if completed by its deadline.

Example

Sorted by profit: J1, J3, J4, J2, J5

J4, J2 skipped — no available slots before deadline

Greedy strategy

Always pick the largest denomination that does not exceed the remaining amount.

Problem

Given arrival and departure times of n trains, find the minimum number of platforms required so that no train waits.

Example

Peak overlap: T2, T3, T4 → 3 platforms

Implementation

def min_platforms(arrivals, departures):
    arrivals.sort()
    departures.sort()
    plat_needed = 0
    max_plat = 0
    i = j = 0

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

    return max_plat

Minimum Spanning Tree (MST)

Given a connected, weighted, undirected graph, find a spanning tree with minimum total edge weight.

Pseudocode (Union-Find)

KRUSKAL(G):
    sort edges by weight
    UF = UnionFind(V)
    mst = []
    for (u, v, w) in sorted_edges:
        if UF.find(u) != UF.find(v):
            mst.append((u, v, w))
            UF.union(u, v)
    return mst

Trace example

Green edges = MST (weight 1+2+3=6). Dashed = rejected.

Pseudocode (binary heap)

PRIM(G, start):
    key[v] = INF for all v
    key[start] = 0
    parent[v] = NIL for all v
    Q = min-heap of all vertices
    while Q not empty:
        u = EXTRACT-MIN(Q)
        for each neighbour v of u:
            if v in Q and w(u,v) < key[v]:
                parent[v] = u
                key[v] = w(u,v)
                DECREASE-KEY(Q, v)
    return parent

Complexity comparison

Problem

Find the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights.

Complexity

Relaxation step

def dijkstra(graph, source):
    dist = {v: float('inf')
            for v in graph}
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq,
                    (dist[v], v))
    return dist

Most widely used shortest-path algorithm — GPS routing, OSPF, game AI pathfinding.

Similarities

• Both require optimal substructure
• Both solve optimisation problems
• Both decompose the problem into sub-problems

Key differences

Decision guide

Classic counter-examples

Why greedy fails

• The locally best choice locks out a combination of future choices that would have been globally better
• There is no "exchange" that can fix the solution
• The problem lacks the greedy choice property, even though it may have optimal substructure

The technique

An exchange argument proves greedy correctness by showing that any optimal solution can be transformed into the greedy solution without loss of quality.

What is a matroid?

A matroid is a pair (S, I) where S is a finite ground set and I is a family of "independent" subsets satisfying:

Examples of matroids

Patterns

Common pitfalls

• Assuming greedy works without proof — the most dangerous mistake; always verify the greedy choice property
• Wrong sorting criterion — activity selection by start time or duration fails; only finish time works
• Confusing fractional and 0/1 — fractional knapsack is greedy; 0/1 is DP
• Ignoring edge cases — empty input, ties in sorting, all items identical
• Negative weights — Dijkstra fails with negative edges; Kruskal/Prim handle them fine

Key takeaways

• Greedy algorithms make locally optimal choices and never backtrack — simple and fast when correct
• Correctness requires the greedy choice property and optimal substructure — prove it or switch to DP
• Activity selection, Huffman coding, and fractional knapsack are canonical greedy problems
• Kruskal's, Prim's, and Dijkstra's are greedy graph algorithms justified by the cut property
• Exchange arguments are the standard proof technique
• Matroid theory gives a complete characterisation of when greedy works
• When greedy fails (0/1 knapsack, non-canonical coins), it often still provides a useful approximation

Recommended reading