Greedy Algorithms

A greedy algorithm builds a solution step by step by making the locally optimal choice at each step. It never reconsiders its decisions. When a problem has greedy choice property and optimal substructure, this simple strategy yields the globally optimal solution.

Greedy Choice Property

The greedy choice property states that a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. In other words, you never need to reconsider a choice once it is made.

Optimal Substructure

Optimal substructure means the optimal solution to the overall problem contains optimal solutions to its subproblems. This property is shared with Dynamic Programming, but greedy algorithms use it differently — they solve one subproblem after another without exploring alternatives.

Huffman Coding

Huffman coding is a greedy algorithm for lossless data compression. It builds a variable-length prefix-free code where more frequent characters get shorter codes and less frequent characters get longer codes.

Algorithm

1. Count the frequency of each character in the input.
2. Create a leaf node for each character and add it to a min-heap (priority queue).
3. While more than one node remains:
   • Extract the two nodes with the smallest frequencies.
   • Create a new internal node with these two as children and frequency equal to their sum.
   • Insert the new node back into the heap.
4. The remaining node is the root of the Huffman tree.
5. Assign codes by traversing the tree (left = 0, right = 1).

import heapq
from collections import Counter

def huffman_encode(data):
    freq = Counter(data)
    heap = [[w, [char, ""]] for char, w in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = "0" + pair[1]
        for pair in hi[1:]:
            pair[1] = "1" + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return sorted(heap[0][1:], key=lambda p: len(p[1]))

# Usage: huffman_encode("abracadabra")

Activity Selection

Given a set of activities with start and end times, select the maximum number of non-overlapping activities. The greedy strategy: always pick the activity with the earliest finish time.

def activity_selection(activities):
    # activities: list of (start, end)
    activities.sort(key=lambda x: x[1])  # sort by finish time
    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

Time complexity: O(n log n) due to sorting.

Fractional Knapsack

Unlike the 0/1 Knapsack (which requires DP), the Fractional Knapsack allows taking fractions of items. The greedy strategy is to take as much as possible of the item with the highest value-to-weight ratio.

def fractional_knapsack(items, capacity):
    # items: list of (value, weight)
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total_value = 0.0
    for value, weight in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

Time complexity: O(n log n). This is the classic "take as much as you can of the most valuable thing."

Traveling Salesman Problem (Approximation)

The Traveling Salesman Problem (TSP) asks: given cities and distances, find the shortest route that visits each city exactly once and returns to the start. TSP is NP-hard, but a simple greedy approximation is the Nearest Neighbor heuristic: start at a city and always visit the nearest unvisited city.

def tsp_nearest_neighbor(graph, start=0):
    n = len(graph)
    visited = [False] * n
    path = [start]
    visited[start] = True
    current = start
    for _ in range(n - 1):
        next_city = min(
            (i for i in range(n) if not visited[i]),
            key=lambda i: graph[current][i]
        )
        visited[next_city] = True
        path.append(next_city)
        current = next_city
    return path

The nearest neighbor heuristic gives a solution within a factor of O(log n) of optimal in the worst case, but often performs much better in practice.

When Greedy Works vs When It Doesn't