S034 · Greedy & Backtracking — When to Use Each

"""gb_lab.py — greedy and backtracking classics side by side."""
from __future__ import annotations
from typing import List, Tuple
 
# ---------- GREEDY: activity selection ----------
def activity_selection(meetings: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """Return the maximum set of non-overlapping meetings (list of (start, end))."""
    meetings = sorted(meetings, key=lambda m: m[1])   # sort by end time
    chosen: List[Tuple[int, int]] = []
    last_end = float("-inf")
    for s, e in meetings:
        if s >= last_end:
            chosen.append((s, e))
            last_end = e
    return chosen
 
# ---------- GREEDY: coin change — works ONLY for canonical currencies ----------
def coin_change_greedy(coins: List[int], amount: int) -> List[int] | None:
    """Greedy: take biggest coin ≤ remaining. Returns None if it fails."""
    coins = sorted(coins, reverse=True)
    used: List[int] = []
    for c in coins:
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None
 
# ---------- GREEDY: Huffman-ish — merge two lowest freq (illustrative) ----------
def huffman_cost(freqs: List[int]) -> int:
    """Total merge cost (LeetCode 1046 style). Real Huffman builds the tree; this is the cost."""
    import heapq
    heap = list(freqs); heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        total += a + b
        heapq.heappush(heap, a + b)
    return total
 
# ---------- BACKTRACKING: N-Queens ----------
def n_queens(n: int) -> List[List[int]]:
    """Return all N-queens solutions as lists where placed[r] = column of row r."""
    solutions: List[List[int]] = []
    placed: List[int] = []
 
    def safe(r: int, c: int) -> bool:
        for pr, pc in enumerate(placed):
            if pc == c or abs(pc - c) == abs(pr - r):
                return False
        return True
 
    def solve(r: int) -> None:
        if r == n:
            solutions.append(placed.copy())        # complete → record
            return
        for c in range(n):
            if safe(r, c):                          # prune
                placed.append(c)                    # choose
                solve(r + 1)                        # recurse
                placed.pop()                        # unchoose
 
    solve(0)
    return solutions
 
# ---------- BACKTRACKING: all subsets (power set) ----------
def all_subsets(nums: List[int]) -> List[List[int]]:
    out: List[List[int]] = []
    cur: List[int] = []
 
    def solve(i: int) -> None:
        if i == len(nums):
            out.append(cur.copy())
            return
        solve(i + 1)                                # branch: skip nums[i]
        cur.append(nums[i])                         # choose
        solve(i + 1)                                # branch: include
        cur.pop()                                   # unchoose
 
    solve(0)
    return out
 
# ---------- BACKTRACKING: all permutations ----------
def all_permutations(nums: List[int]) -> List[List[int]]:
    out: List[List[int]] = []
    used = [False] * len(nums)
    cur: List[int] = []
 
    def solve() -> None:
        if len(cur) == len(nums):
            out.append(cur.copy())
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True; cur.append(x)
            solve()
            used[i] = False; cur.pop()
 
    solve()
    return out
 
# ---------- Demo ----------
if __name__ == "__main__":
    meetings = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),
                (6,10),(8,11),(8,12),(2,14),(12,16)]
    print("Activities:", activity_selection(meetings))          # 4 meetings
 
    print("Coins for 87 (Indian):", coin_change_greedy([1,2,5,10,20,50,100,500], 87))
    print("Coins for 6 (weird [1,3,4]) — greedy:", coin_change_greedy([1,3,4], 6))
    # ↑ Greedy picks 4+1+1 (3 coins); optimum is 3+3 (2 coins). GREEDY FAILS.
 
    print("Huffman cost [4,3,2,6]:", huffman_cost([4, 3, 2, 6]))
 
    print("4-queens solutions:", n_queens(4))                    # 2
    print("8-queens count:", len(n_queens(8)))                   # 92
 
    print("subsets of [1,2,3]:", all_subsets([1, 2, 3]))         # 8
    print("permutations of [1,2,3]:", all_permutations([1, 2, 3]))  # 6