Greedy Algorithms: Activity Selection and Huffman Coding

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. They work when a problem has the greedy choice property and optimal substructure — and they are far simpler than DP when applicable.

# Activity Selection Problem
# Given activities with start and end times, select maximum non-overlapping activities

def activity_selection(activities):
    # Sort by end time (greedy choice: finish earliest to leave most room)
    sorted_acts = sorted(activities, key=lambda x: x[1])
    selected    = [sorted_acts[0]]

    for start, end in sorted_acts[1:]:
        # If this activity starts after the last selected ends
        if start >= selected[-1][1]:
            selected.append((start, end))

    return selected

activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
result = activity_selection(activities)
print(result)  # [(1,4),(5,7),(8,11),(12,16)] — 4 activities

# Fractional Knapsack (greedy works here, unlike 0/1 knapsack!)
def fractional_knapsack(items, capacity):
    # Sort by value/weight ratio (greedy: take most valuable per kg first)
    items = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0.0

    for weight, value in items:
        if capacity >= weight:
            total_value += value
            capacity   -= weight
        else:
            # Take fraction of remaining
            total_value += value * (capacity / weight)
            break

    return total_value

items = [(2,6),(5,10),(10,4),(3,15)]  # (weight, value)
print(fractional_knapsack(items, 12))  # 21.0

Huffman Coding

import heapq

def huffman_encoding(text):
    # Count frequencies
    freq = {}
    for ch in text: freq[ch] = freq.get(ch, 0) + 1

    # Build min-heap: (frequency, char)
    heap = [[f, [ch, ""]] for ch, f 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 dict(sorted(heapq.heappop(heap)[1:], key=lambda x: len(x[1])))

codes = huffman_encoding("ezycoders")
for char, code in sorted(codes.items(), key=lambda x: len(x[1])):
    print(f"  '{char}': {code}")