Greedy

# 1) Interval scheduling — maximise the count of non-overlapping intervals.
#    Greedy: sort by FINISH time, pick earliest-finishing that fits.
#    Correctness: exchange argument — any optimum can be transformed
#    into ours without losing intervals.
def max_meetings(intervals):
    intervals = sorted(intervals, key=lambda x: x[1])
    end = float('-inf'); count = 0; picked = []
    for s, f in intervals:
        if s >= end:
            picked.append((s, f))
            end = f
            count += 1
    return count, picked

print(max_meetings([(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]))
# (4, [(1, 4), (5, 7), (8, 11), (5, 9)?]) — actually 4 intervals when sorted

# 2) Coin change with canonical denominations (Australian: 5,10,20,50,100,200 c)
#    Greedy: largest coin first.
#    Correctness: only works when the denomination system is *canonical*.
#    For arbitrary denominations (e.g. 1, 3, 4 to make 6), use DP instead.
def coins_au(c):
    out = []
    for d in (200, 100, 50, 20, 10, 5):
        n, c = divmod(c, d)
        if n: out.extend([d] * n)
    return out, c     # remaining cents are rounding-not-payable

print(coins_au(287))    # ([200, 50, 20, 10, 5], 2)

# 3) Huffman coding — build an optimal prefix code by greedily merging
#    the two least-frequent symbols.
import heapq
from collections import Counter, defaultdict

def huffman(text):
    h = [[w, [c, '']] for c, w in Counter(text).items()]
    heapq.heapify(h)
    while len(h) > 1:
        lo = heapq.heappop(h)
        hi = heapq.heappop(h)
        for pair in lo[1:]: pair[1] = '0' + pair[1]
        for pair in hi[1:]: pair[1] = '1' + pair[1]
        heapq.heappush(h, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return dict(sorted(h[0][1:], key=lambda p: (len(p[1]), p[0])))

print(huffman('abracadabra'))

# 4) When greedy FAILS — '0/1 knapsack' is the canonical example.
#    Greedy by value/weight ratio can be far from optimal.
#    Use DP (knapsack) or branch-and-bound (TSP) instead.

# 5) Proof patterns to know
# - EXCHANGE: take any optimal solution; show you can swap items in for
#   greedy choices without harming objective. => greedy is optimal.
# - STAYS AHEAD: after k steps, greedy's partial solution dominates any
#   alternative's k-step partial solution. => greedy is optimal.
# - MATROID: if the feasible sets form a matroid, the greedy that picks
#   the best feasible element at each step is optimal (Edmonds).

// Activity selection: pick the next-ending compatible activity.
function maxActivities(items) {
    items.sort((x, y) => x.end - y.end);
    let end = -Infinity, count = 0;
    for (const it of items) if (it.start >= end) { count++; end = it.end; }
    return count;
}