# 1. HUFFMAN CODING
import heapq
import math

def huffman_analysis(frequencies):
    # 1. BUILD THE TREE: Initialize heap with items like (freq, char)
    # Leaf nodes have string characters; internal parent nodes will contain dictionary sub-trees
    heap = [(freq, char) for char, freq in frequencies.items()]
    heapq.heapify(heap)

    # Combine the two smallest elements until only 1 root node remains
    while len(heap) > 1:
        f1, item1 = heapq.heappop(heap)
        f2, item2 = heapq.heappop(heap)
        # Create a parent dictionary mapping left path to '0' and right path to '1'
        parent_structure = {'0': item1, '1': item2}
        heapq.heappush(heap, (f1 + f2, parent_structure))

    # 2. EXTRACT CODES: Traverse our dictionary tree to build bit strings
    codes = {}
    def traverse(node, current_code):
        if isinstance(node, str):  # If it's a string, we hit a leaf character!
            codes[node] = current_code
            return
        # Otherwise, explore left ('0') and right ('1') paths recursively
        traverse(node['0'], current_code + "0")
        traverse(node['1'], current_code + "1")

    root_tree = heap[0][1]
    traverse(root_tree, "")

    # 3. CALCULATE STATS: Compute bit metrics directly using math rules
    huff_bits = sum(frequencies[char] * len(code) for char, code in codes.items())
    
    total_chars = sum(frequencies.values())
    bits_per_char = math.ceil(math.log2(len(frequencies)))  # Minimum fixed bits needed per distinct character
    fixed_bits = total_chars * bits_per_char
    
    saved_bits = fixed_bits - huff_bits

    # 4. OUTPUT RESULTS
    print("Huffman Codes:", codes)
    print(f"Total Huffman Bits: {huff_bits}")
    print(f"Ideal Fixed Bits: {fixed_bits}")
    print(f"Total Bits Saved: {saved_bits}")

# Run code using your sample frequency mapping
char_frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
huffman_analysis(char_frequencies)



# 2. ACTIVITY SELECTION PROBLEM
def activity_selection(start_times, finish_times):
    print("All Available Activities:")
    for i in range(len(start_times)):
        print(f"  Activity {i+1}: Start Time = {start_times[i]} | Finish Time = {finish_times[i]}")
    print("=" * 40)

    activities = sorted(list(zip(start_times, finish_times)), key=lambda x: x[1])
    
    selected_activities = [activities[0]]
    last_finish_time = activities[0][1]
    
    for current_start, current_finish in activities[1:]:
        if current_start >= last_finish_time:
            selected_activities.append((current_start, current_finish))
            last_finish_time = current_finish
            
    print("Selected Activity Schedule:")
    for i, (start, finish) in enumerate(selected_activities, 1):
        print(f"  Activity {i}: Start Time = {start} | Finish Time = {finish}")
        
    print("=" * 40)
    print(f"Total Activities Scheduled: {len(selected_activities)}")
    print("=" * 40)

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


