Greedy Algorithms in Python

What is a Greedy Algorithm?

A greedy algorithm builds a solution step-by-step and at each step chooses what looks best right now.

---

Greedy-Choice Property

A problem has the greedy-choice property if:

✅ Making the best local choice always leads to an optimal global solution.

This is not true for all problems—greedy needs the right structure.

---

When Greedy Works Well

Greedy works well when:

• Local choices never block an optimal solution
• The problem has a provable greedy rule
• Sorting first makes the greedy choices valid (very common)

---

When Greedy Fails

Greedy can fail when a local best choice blocks a better future result.

Example where greedy fails (coin system):

• coins = [1, 3, 4], amount = 6
• greedy picks: 4 + 1 + 1 → 3 coins
• optimal is: 3 + 3 → 2 coins ✅

---

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

Key Greedy Idea

✅ Sort by end time, then always pick the one that ends earliest.

Why it works: Finishing earliest leaves the most room for future activities.

Implementation

def activity_selection(activities):
    # activities = [(start, end), ...]
    activities.sort(key=lambda x: x[1])  # sort by end time
    selected = []

    last_end = float("-inf")
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

acts = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
print(activity_selection(acts))

Complexity

• Time: O(n log n) (sorting)
• Space: O(n) (selected list)

---

Problem: Items have weights and values. You can take fractions of items. Maximize value under capacity.

Greedy Idea

✅ Take items in decreasing order of value/weight ratio.

Why greedy works here: Fractions are allowed, so choosing best density first always stays optimal.

Implementation

def fractional_knapsack(weights, values, capacity):
    items = []
    for w, v in zip(weights, values):
        items.append((v / w, w, v))  # (ratio, weight, value)

    items.sort(reverse=True)  # sort by ratio descending

    total_value = 0
    for ratio, w, v in items:
        if capacity == 0:
            break

        if w <= capacity:
            total_value += v
            capacity -= w
        else:
            total_value += ratio * capacity
            capacity = 0

    return total_value

weights = [10, 20, 30]
values = [60, 100, 120]
print(fractional_knapsack(weights, values, 50))  # 240.0

Complexity

• Time: O(n log n)
• Space: O(n)

---

Huffman coding assigns shorter binary codes to more frequent characters.

Greedy Idea

✅ Repeatedly combine the two least frequent nodes.

Data Structure Used

• Min-heap (priority queue)

Build Huffman Tree

import heapq
from collections import Counter

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

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

def build_huffman_tree(text):
    freq = Counter(text)
    heap = [Node(f, ch) for ch, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = Node(a.freq + b.freq, left=a, right=b)
        heapq.heappush(heap, merged)

    return heap[0] if heap else None

Generate Codes (DFS Traversal)

def generate_codes(root):
    codes = {}

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

    dfs(root, "")
    return codes

text = "aaabbc"
root = build_huffman_tree(text)
print(generate_codes(root))

Complexity

• Heap build: O(k)
• Merging: O(k log k)
  where k = number of unique characters

---

Finds MST of a connected weighted undirected graph.

Greedy Idea

✅ Expand MST by always picking the cheapest edge that connects to a new node.

Implementation (Min Heap)

import heapq

def prim_mst(graph, start=0):
    # graph: {u: [(v, w), ...]}
    visited = set()
    mst_cost = 0
    pq = [(0, start)]  # (weight, node)

    while pq:
        weight, node = heapq.heappop(pq)
        if node in visited:
            continue

        visited.add(node)
        mst_cost += weight

        for neighbor, w in graph[node]:
            if neighbor not in visited:
                heapq.heappush(pq, (w, neighbor))

    return mst_cost

Complexity

• Time: O(E log V)
• Space: O(V + E)

---

Builds MST by picking the globally smallest edges.

Greedy Idea

✅ Sort edges by weight, take the next smallest edge that doesn’t form a cycle.

Needs:

• Union-Find (DSU) to detect cycles efficiently.

Union-Find

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        elif self.rank[ra] > self.rank[rb]:
            self.parent[rb] = ra
        else:
            self.parent[rb] = ra
            self.rank[ra] += 1
        return True

Kruskal Implementation

def kruskal(n, edges):
    # edges: [(w, u, v), ...]
    edges.sort()
    dsu = DSU(n)
    mst_cost = 0
    mst_edges = []

    for w, u, v in edges:
        if dsu.union(u, v):
            mst_cost += w
            mst_edges.append((u, v, w))

    return mst_cost, mst_edges

Complexity

• Sorting edges: O(E log E)
• DSU ops: ~ O(1) amortized
• Total: O(E log E)

---

Greedy algorithms make locally optimal decisions and work when the problem structure guarantees that those local choices lead to a globally optimal solution.

✅ Common Greedy Problems:

• Activity Selection (sort by end time)
• Fractional Knapsack (sort by value density)
• Huffman Coding (merge two smallest using heap)
• MST: Prim’s (expand using min edge), Kruskal’s (sort edges + DSU)