Level 3 · 35 min

Greedy Algorithms: Exchange Arguments

A greedy algorithm makes the locally best choice and never revisits it. The hard part is proving the local choice is globally safe.

Greedy is not a vibe

Sorting by a convenient key and taking the first valid option is only greedy if you can prove the choice is safe. Counterexamples are common: coin change works for some denominations and fails for others; shortest processing time optimizes one objective but not all scheduling objectives.

Exchange arguments

An exchange proof shows that any optimal solution can be transformed to include the greedy choice without making it worse. For interval scheduling, choosing the activity that finishes earliest is safe because any optimal schedule can swap its first activity for the earliest-finishing compatible one.

Matroids and cut properties

Some problem families have structure that guarantees greedy correctness. Minimum spanning tree algorithms use cut properties: the lightest edge crossing a safe cut can be added to some MST. Huffman coding repeatedly merges the two lowest frequencies because an optimal prefix code can be arranged with them as deepest siblings.

Key Takeaways

Greedy algorithms need a correctness proof, usually exchange, cut property, or invariant.
A local choice is safe when an optimal solution can be made to include it.
If a counterexample exists, the problem probably needs DP, search, or a different objective.

Code example

function intervalSchedule(intervals):
  sort intervals by endTime ascending
  chosen = []
  lastEnd = negativeInfinity
  for interval in intervals:
    if interval.start >= lastEnd:
      chosen.append(interval)
      lastEnd = interval.end
  return chosen