# 1. HUFFMAN CODING
import heapq
import itertools
import math


def huffman_analysis(frequencies):
    if not frequencies:
        print("Huffman Codes: {}")
        print("Total Huffman Bits: 0")
        print("Ideal Fixed Bits: 0")
        print("Total Bits Saved: 0")
        return

    order = itertools.count()
    heap = [(freq, next(order), char) for char, freq in frequencies.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        freq1, _, left = heapq.heappop(heap)
        freq2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (freq1 + freq2, next(order), (left, right)))

    codes = {}

    def visit(node, code):
        if isinstance(node, str):
            codes[node] = code
        else:
            visit(node[0], code + "0")
            visit(node[1], code + "1")

    visit(heap[0][2], "")
    huffman_bits = sum(frequencies[char] * len(code) for char, code in codes.items())
    total_chars = sum(frequencies.values())
    fixed_bits = total_chars * math.ceil(math.log2(len(frequencies))) if len(frequencies) > 1 else 0

    print("Huffman Codes:", codes)
    print(f"Total Huffman Bits: {huffman_bits}")
    print(f"Ideal Fixed Bits: {fixed_bits}")
    print(f"Total Bits Saved: {fixed_bits - huffman_bits}")


frequencies = {"a": 5, "b": 9, "c": 12, "d": 13, "e": 16, "f": 45}
huffman_analysis(frequencies)


# 2. ACTIVITY SELECTION PROBLEM
def activity_selection(starts, finishes):
    if len(starts) != len(finishes):
        raise ValueError("Start and finish lists must have the same length.")

    activities = sorted(zip(starts, finishes), key=lambda activity: activity[1])
    selected = []

    for start, finish in activities:
        if not selected or start >= selected[-1][1]:
            selected.append((start, finish))

    for i, (start, finish) in enumerate(selected, 1):
        print(f"Activity {i}: Start Time = {start} | Finish Time = {finish}")
    print(f"Total Activities Scheduled: {len(selected)}")
    return selected


starts = [1, 3, 0, 5, 8, 5]
finishes = [2, 4, 6, 7, 9, 9]
activity_selection(starts, finishes)
