How It Works

Most greedy algorithms share the same skeleton. Put the candidates in sorted order or into a priority queue, take them out one at a time, and accept each one that does not conflict with the choices made so far. This chapter traces interval scheduling, Huffman coding and meeting-room allocation on small examples.

Interval scheduling (activity selection)

One meeting room has received several requests, and you want to fit in as many meetings as possible without overlaps. Each meeting is a half-open interval [start, end), so a meeting ending at 4 lets the next one start at 4. The greedy rule is "take the meeting that ends first".

def trace(intervals):
    last_end = float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        ok = start >= last_end
        print(f"({start}, {end}) last_end={last_end} -> {'take' if ok else 'skip'}")
        if ok:
            last_end = end


trace([(1, 3), (2, 5), (4, 7), (1, 8), (6, 9), (8, 10)])

After sorting by end time, the scan goes like this.

The result is (1, 3), (4, 7), (8, 10): three meetings, and no schedule can hold more.

Why other rules fail

Rules that sound reasonable collapse under a single counterexample.

Taking the meeting that ends first leaves the most time for everything else. By induction, the k-th meeting chosen by greedy ends no later than the k-th meeting of any other valid schedule; that is the "greedy stays ahead" argument.

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.