5 min read
On this page

Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping to reach a globally optimal solution. Greedy works when the problem has greedy choice property and optimal substructure.

When Does Greedy Work?

Greedy Choice Property

A globally optimal solution can be reached by making locally optimal choices. The greedy choice doesn't need to consider future consequences.

Optimal Substructure

An optimal solution to the problem contains optimal solutions to its subproblems.

Key difference from DP: Greedy makes one choice and moves forward (no backtracking). DP considers all choices and picks the best.

Proving Greedy Correctness

Exchange argument: Show that any optimal solution can be transformed into the greedy solution without worsening it. Typically:

  1. Assume an optimal solution OPT differs from the greedy solution G.
  2. Find the first point of difference.
  3. Show that swapping OPT's choice for G's choice doesn't worsen the solution.
  4. Repeat until OPT = G.

Greedy stays ahead: Show by induction that after each step, the greedy solution is at least as good as any other solution at that step.

Classic Problems

Activity Selection

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

Greedy: Sort by finish time. Select each activity if it doesn't overlap with the last selected.

FUNCTION ACTIVITY_SELECTION(activities)
    SORT activities BY finish time
    selected ← [activities[0]]

    FOR EACH (start, finish) IN activities[1..]
        IF start ≥ last element of selected .finish
            APPEND (start, finish) TO selected
    RETURN selected

Time: O(n log n) (sorting dominates).

Why sort by finish time? Choosing the earliest-finishing activity leaves the most room for subsequent activities. Proven by exchange argument.

Fractional Knapsack

Given items with weights and values, and a knapsack with capacity W, maximize total value. Items can be fractioned.

Greedy: Sort by value/weight ratio (descending). Take items greedily.

FUNCTION FRACTIONAL_KNAPSACK(items, capacity)
    SORT items BY value/weight ratio (descending)

    total_value ← 0
    remaining ← capacity

    FOR EACH (value, weight) IN items
        IF remaining ≥ weight
            total_value ← total_value + value
            remaining ← remaining - weight
        ELSE
            total_value ← total_value + value * (remaining / weight)   // take fraction
            BREAK
    RETURN total_value

Note: This does NOT work for 0/1 knapsack (where items can't be fractioned). 0/1 knapsack requires DP.

Huffman Coding

Build an optimal prefix code for data compression. Characters with higher frequency get shorter codes.

Algorithm:

  1. Create a leaf node for each character with its frequency.
  2. Insert all nodes into a min-heap (priority queue).
  3. While the heap has more than one node: a. Extract the two nodes with smallest frequency. b. Create a new internal node with these as children. Frequency = sum of children's frequencies. c. Insert the new node back into the heap.
  4. The remaining node is the root of the Huffman tree.
FUNCTION HUFFMAN(freqs)
    heap ← MIN_HEAP
    FOR EACH (char, freq) IN freqs
        INSERT Leaf(char, freq) INTO heap

    WHILE size(heap) > 1
        (f1, n1) ← EXTRACT_MIN(heap)
        (f2, n2) ← EXTRACT_MIN(heap)
        INSERT Internal(n1, n2, freq: f1 + f2) INTO heap

    RETURN EXTRACT_MIN(heap)

Time: O(n log n). Optimality: Huffman coding produces the optimal prefix code (minimum expected code length).

Code assignment: Left edge = 0, right edge = 1. Code for a character = path from root to leaf.

Minimum Spanning Trees

Kruskal's (greedy by edge weight) and Prim's (greedy by closest vertex) — both covered in data structures topic 02.

Greedy property: The cut property guarantees that the lightest edge crossing any cut is safe to add.

Dijkstra's Shortest Path

Greedy by nearest unvisited vertex. Extract the vertex with smallest tentative distance, relax its edges.

FUNCTION DIJKSTRA(graph, source)
    n ← number of vertices in graph
    dist ← array of size n, all set to INFINITY
    dist[source] ← 0
    heap ← MIN_HEAP containing (0, source)

    WHILE heap is not empty
        (d, u) ← EXTRACT_MIN(heap)
        IF d > dist[u] THEN CONTINUE   // stale entry
        FOR EACH (v, w) IN neighbors of u
            new_dist ← d + w
            IF new_dist < dist[v]
                dist[v] ← new_dist
                INSERT (new_dist, v) INTO heap
    RETURN dist

Time: O((V + E) log V) with binary heap. O(E + V log V) with Fibonacci heap.

Correctness: When a vertex is extracted from the heap, its distance is final. Requires non-negative edge weights.

Job Scheduling

Weighted Job Scheduling with Deadlines

Each job has a profit and deadline. Schedule jobs to maximize profit, where each job takes unit time.

Greedy: Sort by profit (descending). For each job, assign it to the latest available slot before its deadline.

Minimizing Lateness

Jobs have processing times and deadlines. Schedule to minimize maximum lateness.

Greedy: Sort by deadline (Earliest Deadline First). Proven optimal by exchange argument.

Matroid Theory

A matroid is a combinatorial structure where greedy always works.

Definition: A matroid (S, I) has ground set S and a family of "independent" sets I satisfying:

  1. ∅ ∈ I (empty set is independent).
  2. If A ∈ I and B ⊆ A, then B ∈ I (hereditary property).
  3. If A, B ∈ I and |A| < |B|, then ∃x ∈ B\A such that A ∪ {x} ∈ I (exchange/augmentation property).

Key theorem: A greedy algorithm finds the maximum-weight independent set in a matroid.

Examples of matroids:

  • Graphic matroid: Ground set = edges. Independent = acyclic subsets (forests). Maximum weight independent set = MST.
  • Uniform matroid: Independent = sets of size ≤ k. Maximum weight = top-k elements.
  • Partition matroid: Ground set partitioned into groups. Independent = at most one element per group.

Non-matroids: 0/1 knapsack is NOT a matroid (greedy doesn't work). TSP is not a matroid.

Greedy vs DP

| Aspect | Greedy | Dynamic Programming | |---|---|---| | Strategy | Make one choice, move on | Try all choices, pick best | | Correctness | Need proof (exchange, matroid) | Always correct (if formulated right) | | Efficiency | Usually faster (one pass) | Slower (fills a table) | | Space | Often O(1) extra | Often O(n) or O(n²) | | When to use | Problem has greedy choice property | Overlapping subproblems | | Example | Fractional knapsack | 0/1 knapsack |

Tip: If greedy gives the wrong answer on a small example, use DP. If greedy works on all examples, try to prove it (exchange argument or matroid structure).

Applications in CS

  • Compression: Huffman coding (gzip, DEFLATE), Lempel-Ziv (greedy longest match).
  • Networking: Dijkstra (OSPF routing), Prim/Kruskal (network design), greedy scheduling (SRPT for shortest job first).
  • Operating systems: Shortest Job First (SJF) scheduling, greedy memory allocation (first fit, best fit).
  • Machine learning: Greedy feature selection, decision tree splitting (greedy by information gain), greedy decoding (beam search).
  • Approximation algorithms: Greedy set cover (O(log n) approximation), greedy vertex cover (2-approximation).