This chapter implements two classic greedy algorithms in Python, interval scheduling and Huffman code lengths, then ports interval scheduling to C++, Java and TypeScript.
Python
import heapq
def max_non_overlapping(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
"""Most pairwise-disjoint half-open intervals [start, end)."""
chosen: list[tuple[int, int]] = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
def huffman_code_lengths(freq: dict[str, int]) -> dict[str, int]:
"""Return the bit length of each symbol's Huffman code."""
symbols = list(freq)
if len(symbols) <= 1:
return {s: 1 for s in symbols}
heap = [(w, i) for i, w in enumerate(freq.values())]
heapq.heapify(heap)
parent = [-1] * len(symbols) # node id -> parent id; ids >= n are internal
while len(heap) > 1:
w1, a = heapq.heappop(heap)
w2, b = heapq.heappop(heap)
node = len(parent)
parent.append(-1)
parent[a] = parent[b] = node
heapq.heappush(heap, (w1 + w2, node))
depth = [0] * len(parent)
for node in range(len(parent) - 2, -1, -1):
depth[node] = depth[parent[node]] + 1
return {s: depth[i] for i, s in enumerate(symbols)}
max_non_overlapping, line by line
sorted(..., key=lambda iv: iv[1]) returns a new list ordered by end time; the input is untouched.last_end starts at minus infinity, so the first interval is always accepted.start >= last_end: a half-open interval may start exactly when the previous one ends. Use > for closed intervals.- Thanks to the sort, each candidate is compared with
last_end only, never with earlier choices.
huffman_code_lengths, line by line
- A lone symbol still needs one bit, so zero or one symbol returns length 1.
- The heap holds
(weight, node id); ids break ties deterministically and never raise TypeError. - The greedy step pops the two lightest nodes, links them to a new internal node, and pushes the merged weight back.
- A parent's id is always larger than its children's, so walking ids downward fills in parent depths first. The last node is the root, at depth 0.
- Depth equals code length; canonical Huffman codes can be built from it.
Usage
from collections import Counter
meetings = [(1, 3), (2, 5), (4, 7), (1, 8), (6, 9), (8, 10)]
print(max_non_overlapping(meetings)) # [(1, 3), (4, 7), (8, 10)]
lengths = huffman_code_lengths({"a": 5, "b": 9, "c": 12, "d": 13, "e": 16, "f": 45})
print(lengths) # {'a': 4, 'b': 4, 'c': 3, 'd': 3, 'e': 3, 'f': 1}
text = "abracadabra"
counts = Counter(text)
bits = sum(counts[s] * n for s, n in huffman_code_lengths(counts).items())
print(bits, "bits vs", 8 * len(text), "at 8 bits each") # 23 bits vs 88 at 8 bits each
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.