Greedy algorithms and intervals

Prove a greedy choice with an exchange argument, schedule and merge intervals, build a Huffman code, and recognise when greedy fails.

Why greedy is right, and when it is not

A greedy algorithm commits to a locally best choice and never reconsiders. It is correct only when the problem has the greedy-choice property and optimal substructure. The proof is usually an exchange argument: take any optimal solution, swap its first choice for the greedy one, and show the result is no worse.

from typing import Sequence

def coin_change_greedy(coins: Sequence[int], amount: int) -> list[int] | None:
    """CORRECT for canonical systems such as [1, 5, 10, 25]."""
    out: list[int] = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            out.append(c)
    return None if amount else out


def coin_change_dp(coins: Sequence[int], amount: int) -> int:
    """Always correct. Greedy on [1, 3, 4] with 6 gives 4+1+1 = 3 coins;
    the optimum is 3+3 = 2, so greedy is wrong there and this is the answer."""
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return -1 if best[amount] == INF else int(best[amount])


def best_time_to_buy(prices: Sequence[int]) -> int:
    """Greedy in one pass: track the minimum so far and the best gain."""
    low = prices[0]
    gain = 0
    for p in prices[1:]:
        gain = max(gain, p - low)
        low = min(low, p)
    return gain


def can_jump(nums: Sequence[int]) -> bool:
    """Track the furthest reachable index; never look back."""
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False          # this index is unreachable
        reach = max(reach, i + step)
    return True


if __name__ == "__main__":
    print(coin_change_greedy([25, 10, 5, 1], 63))
    print(coin_change_greedy([4, 3, 1], 6))     # [4, 1, 1], which is not optimal
    print(coin_change_dp([4, 3, 1], 6))         # 2
    print(best_time_to_buy([7, 1, 5, 3, 6, 4]))  # 5
    print(can_jump([2, 3, 1, 1, 4]))            # True

Interval scheduling and merging

from typing import Sequence

Interval = tuple[int, int]      # half open: [start, end)

def max_non_overlapping(intervals: Sequence[Interval]) -> int:
    """Sort by finishing time: the earliest finish leaves the most room."""
    if not intervals:
        return 0
    ordered = sorted(intervals, key=lambda iv: iv[1])
    count = 0
    last_end = float("-inf")
    for start, end in ordered:
        if start >= last_end:          # >= for half open intervals
            count += 1
            last_end = end
    return count


def merge_intervals(intervals: Sequence[Interval]) -> list[Interval]:
    """Sort by start, then extend the current interval while it overlaps."""
    if not intervals:
        return []
    ordered = sorted(intervals)
    out = [ordered[0]]
    for start, end in ordered[1:]:
        last_start, last_end = out[-1]
        if start <= last_end:                       # overlapping or touching
            out[-1] = (last_start, max(last_end, end))
        else:
            out.append((start, end))
    return out


def min_meeting_rooms(intervals: Sequence[Interval]) -> int:
    """Sweep line: a heap of end times gives the peak concurrent count."""
    import heapq
    if not intervals:
        return 0
    ordered = sorted(intervals)
    ends: list[int] = []
    for start, end in ordered:
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)     # reuse a room that has freed up
        else:
            heapq.heappush(ends, end)
    return len(ends)


def insert_interval(intervals: Sequence[Interval], new: Interval) -> list[Interval]:
    """Sorted input: append what comes before, absorb the overlap, append the rest."""
    out: list[Interval] = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < new[0]:
        out.append(intervals[i]); i += 1
    start, end = new
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    out.append((start, end))
    out.extend(intervals[i:])
    return out


if __name__ == "__main__":
    print(max_non_overlapping([(1, 3), (2, 5), (4, 7), (6, 9)]))   # 2
    print(merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]))
    print(min_meeting_rooms([(0, 30), (5, 10), (15, 20)]))          # 2

• The correct sorting key is the whole algorithm. Sorting by start time gives a suboptimal answer for maximum non-overlapping intervals; sorting by finish time is provably optimal.
• Half-open intervals [start, end) use start >= last_end; closed intervals [start, end] use start > last_end. Mixing the two conventions is the most common off-by-one in interval code.
• The sweep-line plus heap pattern answers every concurrency question: peak overlap, minimum resources, and maximum simultaneous events.
• A heap of end times is enough because the start times are already processed in sorted order. No interval tree is required.

Huffman coding

import heapq
from collections import Counter
from dataclasses import dataclass, field

@dataclass(order=True)
class HuffNode:
    freq: int
    symbol: str | None = field(compare=False, default=None)
    left: "HuffNode | None" = field(compare=False, default=None)
    right: "HuffNode | None" = field(compare=False, default=None)


def build_huffman(text: str) -> HuffNode:
    """Repeatedly merge the two least frequent nodes."""
    heap = [HuffNode(freq, symbol) for symbol, freq in Counter(text).items()]
    if len(heap) == 1:
        # a single distinct symbol still needs a root with a child
        only = heapq.heappop(heap)
        return HuffNode(only.freq, None, only, None)

    heapq.heapify(heap)
    while len(heap) > 1:
        a = heapq.heappop(heap)          # the least frequent
        b = heapq.heappop(heap)          # the second least frequent
        heapq.heappush(heap, HuffNode(a.freq + b.freq, None, a, b))
    return heap[0]


def codes(root: HuffNode) -> dict[str, str]:
    out: dict[str, str] = {}

    def walk(node: HuffNode | None, prefix: str) -> None:
        if node is None:
            return
        if node.symbol is not None:
            out[node.symbol] = prefix or "0"     # a one-symbol alphabet needs a bit
            return
        walk(node.left, prefix + "0")
        walk(node.right, prefix + "1")

    walk(root, "")
    return out


def encode(text: str, table: dict[str, str]) -> str:
    return "".join(table[ch] for ch in text)


def weighted_path_length(root: HuffNode) -> int:
    """The total encoded length: this is what Huffman minimises."""
    def walk(node: HuffNode | None, depth: int) -> int:
        if node is None:
            return 0
        if node.symbol is not None:
            return node.freq * depth
        return walk(node.left, depth + 1) + walk(node.right, depth + 1)
    return walk(root, 0)


if __name__ == "__main__":
    text = "abracadabra"
    tree = build_huffman(text)
    table = codes(tree)
    print(table)
    print(len(encode(text, table)), "bits vs", len(text) * 8, "bits fixed width")
    print(weighted_path_length(tree))

FAQ

Related

Union-Find and minimum spanning trees Heaps, priority queues and top-k problems

Last refreshed 2026-09-18.