algo-greedy

name	algo-greedy
description	Greedy algorithms — exchange-argument proofs, when greedy beats DP, classic patterns (interval scheduling, Huffman, scheduling).
when-to-use	Interval scheduling, activity selection, minimum-spanning-tree weights, Huffman codes, fractional knapsack, scheduling with deadlines.

Greedy — locally best, prove globally optimal

Greedy algorithms make the locally optimal choice at every step and never reconsider. They are the right tool when an "exchange argument" works: any optimal solution can be transformed into the greedy solution without losing optimality.

Invariants

• The greedy choice is safe: there exists an optimal solution consistent with that choice.
• The remaining problem is the same shape (optimal substructure) but smaller.
• If you cannot prove safety, greedy is probably wrong — DP or search is the fallback.

Complexity

• Most greedy algorithms are dominated by an O(n log n) sort step.
• Min-heap based greedy (Dijkstra, Prim, Huffman) is O((V + E) log V) or O(n log n).
• Linear-scan greedy (jump game, gas station) is O(n).

Template — Python (interval scheduling — earliest end time)

def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:
    """Maximum number of non-overlapping intervals (start, end)."""
    intervals.sort(key=lambda iv: iv[1])  # sort by end
    count = 0
    end = float("-inf")
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

The exchange-argument proof: pick any optimal schedule's first interval O; replace it with the earliest-ending interval G. G ends no later than O, so the rest of the schedule still fits. Repeat. The greedy schedule has at least as many intervals.

Template — Python (Huffman coding — repeatedly merge two smallest)

import heapq

def huffman_cost(weights: list[int]) -> int:
    """Total cost of an optimal binary prefix code (sum of code lengths × freq)."""
    heap = list(weights)
    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

The merging-pair argument: in any optimal prefix tree, the two lowest-frequency leaves are siblings at the deepest level. Merging them into one node reduces the problem by 1, and the optimal solution to the sub-problem extends to the original.

Template — JavaScript (jump game — farthest reachable)

function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;          // cannot reach i
    reach = Math.max(reach, i + nums[i]); // extend horizon
  }
  return true;
}

reach is the invariant: "farthest index reachable from the prefix [0..i]". Each step either extends the horizon or fails.

Common pitfalls

• Greedy on the wrong key. "Earliest end" works for interval scheduling; "shortest" or "earliest start" do not. Test small counterexamples before coding the production version.
• Greedy where DP is needed. Coin change with arbitrary denominations is the canonical DP-vs-greedy trap: [1, 3, 4], target 6 — greedy picks 4+1+1 (3 coins), DP picks 3+3 (2 coins).
• Forgetting the sort. Most greedy algorithms hinge on a sort by the right key. Skipping it gives wrong answers on adversarial input.
• Tie-breaking matters. Two intervals ending at the same time: pick the one with the latest start to maximise headroom. The default sort is stable but not necessarily optimal — be explicit.
• Reasoning by example. Two examples can both work and your greedy still be wrong on the third. Demand an exchange argument or a counterexample search.

Test corner cases

• Empty input.
• Single element.
• All elements identical.
• Adversarial ordering (reverse-sorted, alternating).
• Ties at the greedy-key — ensure tie-breaking is correct.
• Edge-of-range constraints (interval ending exactly when next starts — does the schedule allow it?).

When the problem says "minimum number of X" or "maximum number of non-conflicting Y", greedy is a strong first guess. When it says "minimum cost to achieve goal Z", DP is the safer first guess.