Greedy algorithms

pythondef select_activities(activities):
    """activities: list of (start, finish). Return a max non-overlapping subset."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(activities, key=lambda a: a[1]):  # earliest finish first
        if start >= last_finish:            # compatible with the last chosen
            chosen.append((start, finish))
            last_finish = finish
    return chosen

acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
picked = select_activities(acts)
print("selected", len(picked), "activities:", picked)

pythonimport heapq

def min_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])      # by start time
    heap = []                               # end times of rooms in use (min at top)
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)             # a room freed up -> reuse it
        heapq.heappush(heap, end)
    return len(heap)                        # rooms never freed = peak overlap

meetings = [(0, 30), (5, 10), (15, 20)]
print("rooms needed:", min_rooms(meetings))            # 2
print("rooms:", min_rooms([(1, 5), (2, 6), (3, 7), (8, 9)]))  # 3

pythonimport heapq
from collections import Counter

def huffman_codes(text):
    freq = Counter(text)
    if len(freq) == 1:                      # single-symbol edge case
        return {next(iter(freq)): "0"}
    # nodes as (freq, tie_id, node); node is a symbol str or a (left, right) tuple
    nodes = [(f, i, sym) for i, (sym, f) in enumerate(freq.items())]
    heapq.heapify(nodes)
    counter = len(nodes)
    while len(nodes) > 1:
        f1, _, n1 = heapq.heappop(nodes)    # two rarest
        f2, _, n2 = heapq.heappop(nodes)
        heapq.heappush(nodes, (f1 + f2, counter, (n1, n2)))
        counter += 1
    root = nodes[0][2]

    codes = {}
    def walk(node, prefix):  # noqa
        if isinstance(node, str):
            codes[node] = prefix or "0"
        else:
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
    walk(root, "")
    return codes

text = "abracadabra"
codes = huffman_codes(text)
encoded_bits = sum(len(codes[c]) for c in text)
print("codes:", {k: codes[k] for k in sorted(codes)})
print("Huffman bits:", encoded_bits, "vs fixed 3-bit:", 3 * len(text))

pythondef fractional_knapsack(items, W):
    """items: list of (value, weight). Return max value for capacity W."""
    items = sorted(items, key=lambda it: it[0] / it[1], reverse=True)  # densest first
    total = 0.0
    for value, weight in items:
        if W <= 0:
            break
        take = min(weight, W)               # take a fraction of the last item
        total += value * (take / weight)
        W -= take
    return round(total, 2)

items = [(60, 10), (100, 20), (120, 30)]    # (value, weight)
print("fractional, W=50:", fractional_knapsack(items, 50))   # 240.0
print("fractional, W=25:", fractional_knapsack(items, 25))

pythondef greedy_01(items, W):
    items = sorted(items, key=lambda it: it[0] / it[1], reverse=True)
    total, w = 0, 0
    for value, weight in items:
        if w + weight <= W:                 # 0/1: take whole item or none
            total += value; w += weight
    return total

def dp_01(items, W):
    dp = [0] * (W + 1)
    for value, weight in items:
        for cap in range(W, weight - 1, -1):
            dp[cap] = max(dp[cap], value + dp[cap - weight])
    return dp[W]

items = [(60, 10), (100, 20), (120, 30)]    # (value, weight)
W = 50
print("greedy 0/1:", greedy_01(items, W), " DP 0/1:", dp_01(items, W))