• When Greedy Works
• Classic Greedy Algorithms
• Matroid Theory Primer
• Greedy Correctness via Matroids
• Exchange Argument
• Pitfalls and Counterexamples
• Exercises

A greedy algorithm builds a solution step-by-step by choosing the locally optimal option hoping to reach a global optimum. It is efficient and simple but requires a greedy-choice property and often optimal substructure.

• Time: typically O(n log n) due to sorting or priority queues
• Space: O(1)–O(n)
• Proof tools: exchange argument, cut property, matroid structure

• Interval scheduling (max non-overlapping): sort by earliest finish time.
• Huffman coding: repeatedly merge two least frequent symbols using a min-heap.
• Minimum spanning tree: Kruskal (sort edges, DSU) and Prim (PQ) via cut property.
• Activity selection / Room scheduling: variations of interval scheduling.
• Canoeist/boat pairing, coin change (canonical coin systems): greedy by value or ratios.

// Interval scheduling: select max non-overlapping intervals
function maxNonOverlapping(intervals) {
  intervals.sort((a,b) => a[1] - b[1]);
  let count = 0, end = -Infinity;
  for (const [s,e] of intervals) {
    if (s >= end) { count++; end = e; }
  }
  return count;
}

A matroid M = (E, I) consists of a ground set E and a family I of independent subsets satisfying:

1) Non-empty: ∅ ∈ I
2) Hereditary: if A ∈ I and B ⊆ A then B ∈ I
3) Exchange: if A, B ∈ I and |A| > |B| then ∃ e ∈ A \ B such that B ∪ {e} ∈ I

Examples: graphic matroid (forests in a graph), partition matroid, uniform matroid, transversal matroid.

For a weighted matroid, the greedy algorithm that processes elements in decreasing weight and extends any independent set yields a maximum-weight independent set. This generalizes Kruskal's algorithm on graphic matroids.

Greedy theorem: In any matroid, greedy produces a maximum-weight base.

The exchange argument shows that any optimal solution can be transformed step-by-step to the greedy solution without worsening cost, by exchanging elements while preserving feasibility.

• Coin change (non-canonical systems): greedy fails; need DP.
• Knapsack (0/1): greedy by value/weight ratio is not optimal.
• Scheduling with deadlines and durations: choice may depend on future interactions.

1. Prove interval scheduling correctness via exchange argument.
2. Implement Kruskal with DSU and prove correctness using cut property.
3. Construct a coin system where greedy fails but DP works.