How It Works

Huffman coding

Huffman coding builds a prefix code that gives short bit strings to frequent symbols and long ones to rare symbols, minimizing the total length. The greedy rule is "merge the two lightest groups". Let's follow the frequencies a=5, b=9, c=12, d=13, e=16, f=45.

import heapq

freq = {"a": 5, "b": 9, "c": 12, "d": 13, "e": 16, "f": 45}
heap = [(w, ch) for ch, w in freq.items()]
heapq.heapify(heap)
total = 0
while len(heap) > 1:
    w1, x = heapq.heappop(heap)
    w2, y = heapq.heappop(heap)
    total += w1 + w2
    print(f"{x}({w1}) + {y}({w2}) = {w1 + w2}")
    heapq.heappush(heap, (w1 + w2, x + y))
print("total bits:", total)  # 224

In the finished tree f sits at depth 1, c, d and e at depth 3, and a and b at depth 4. Each symbol's code length equals its depth, and the sum of frequency times length is 45 + 36 + 39 + 48 + 20 + 36 = 224 bits, the same as the sum of all merged weights (14 + 25 + 30 + 55 + 100). A fixed 3-bit code would need 300 bits, so Huffman saves about 25%.

An exchange argument shows that some optimal tree places the two lightest symbols as siblings at the deepest level: if a heavier symbol were deeper, swapping the two could not increase the cost.

Meeting rooms (minimum platforms)

Now every meeting must take place, and you want the minimum number of rooms. Counting the platforms a railway station needs is the same problem. Scan meetings by start time and keep the end times of rooms in use in a min-heap. If the room that frees up first is free by the time the meeting starts, reuse it; otherwise open a new room.

import heapq


def min_rooms(meetings):
    ends = []  # end times of rooms in use (min-heap)
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)  # reuse the room that frees up first
        else:
            heapq.heappush(ends, end)     # open a new room
    return len(ends)


print(min_rooms([(9, 10), (9, 12), (10, 11), (11, 13), (12, 13)]))  # 2

If, as with train platforms, an arrival and a departure at the same minute cannot share a platform, change ends[0] <= start to ends[0] < start. Whether interval endpoints are inclusive is the most common source of greedy bugs.

Summary

• The greedy skeleton is: sort or heapify by a rule, take items one by one, accept those that do not conflict.
• Interval scheduling takes the earliest end, Huffman merges the two lightest groups, room allocation reuses the room that frees up first.
• Plausible alternative rules break on tiny counterexamples, so always be able to say why your rule is right.
• Decide inclusive versus exclusive endpoints (< versus <=) from the problem statement.