Greedy Algorithms¶

def max_activities(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Maximize count of non-overlapping intervals. Sort by END time — the
    provably optimal greedy rule for this problem (NOT start time, NOT duration)."""
    if not intervals:
        return []

    sorted_intervals = sorted(intervals, key=lambda iv: iv[1])
    selected = [sorted_intervals[0]]
    last_end = sorted_intervals[0][1]

    for start, end in sorted_intervals[1:]:
        if start >= last_end:  # compatible — doesn't overlap the last accepted interval
            selected.append((start, end))
            last_end = end

    return selected
    # Time: O(n log n) for the sort, O(n) for the single pass
    # Space: O(n) for the result

import heapq
from collections import Counter

class HuffmanNode:
    def __init__(self, freq: int, char: str | None = None, left=None, right=None):
        self.freq = freq; self.char = char; self.left = left; self.right = right
    def __lt__(self, other):  # heap needs a total order
        return self.freq < other.freq

def build_huffman_tree(text: str) -> HuffmanNode:
    """Greedy: always merge the two least-frequent nodes. Minimizes weighted path
    length = expected code length, which is exactly what compression wants."""
    freq = Counter(text)
    heap = [HuffmanNode(f, ch) for ch, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, merged)

    return heap[0]
    # Time: O(k log k) where k = number of distinct characters


def build_codes(node: HuffmanNode, prefix: str = "", codes: dict[str, str] | None = None) -> dict[str, str]:
    if codes is None:
        codes = {}
    if node.char is not None:  # leaf
        codes[node.char] = prefix or "0"  # handle single-character input
        return codes
    build_codes(node.left, prefix + "0", codes)
    build_codes(node.right, prefix + "1", codes)
    return codes
    # Frequent characters end up near the root → short codes.
    # Result is prefix-free: no code is a prefix of another, so decoding is unambiguous.

def fractional_knapsack(items: list[tuple[int, int]], capacity: int) -> float:
    """items: (value, weight). Greedy on value/weight ratio — valid ONLY because
    items can be split. 0/1 knapsack (whole items only) requires DP instead."""
    items = sorted(items, key=lambda iv: iv[0] / iv[1], reverse=True)
    total_value = 0.0
    remaining = capacity

    for value, weight in items:
        if remaining <= 0:
            break
        take = min(weight, remaining)
        total_value += value * (take / weight)
        remaining -= take

    return total_value
    # Time: O(n log n) for the sort

def can_jump(nums: list[int]) -> bool:
    """Track the farthest index reachable so far — greedy because reaching
    farther is never worse than reaching less far, from any position."""
    farthest = 0
    for i, num in enumerate(nums):
        if i > farthest:
            return False  # this index is unreachable, and nothing later can be either
        farthest = max(farthest, i + num)
    return True
    # Time: O(n)  Space: O(1)

import heapq

def min_meeting_rooms(intervals: list[tuple[int, int]]) -> int:
    """Sort by start; use a heap of active end times to track concurrent overlap."""
    if not intervals:
        return 0

    intervals = sorted(intervals, key=lambda iv: iv[0])
    heap = []  # end times of rooms currently in use

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)  # earliest-ending room freed up before this meeting starts
        heapq.heappush(heap, end)

    return len(heap)  # max concurrent rooms needed
    # Time: O(n log n)  Space: O(n)

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    """If total gas >= total cost, a valid start exists. Greedy: whenever the
    running tank goes negative, no station up to here can be the start — reset."""
    if sum(gas) < sum(cost):
        return -1

    tank, start = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1  # this station, and none before it up to here, can start
            tank = 0

    return start
    # Time: O(n)  Space: O(1)