Greedy Exchange Argument
A proof pattern for showing that one locally optimal choice can be forced into some global optimum without making the solution worse.
Greedy Exchange Argument
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Greedy solutions are common in competitive programming, but the hard part is often not spotting the greedy rule. It is proving that the local choice does not paint the solution into a corner. The exchange argument is the proof shape I use most often for that.
When to Use It
Reach for an exchange argument when:
the algorithm repeatedly chooses the ``best'' next item under some ordering,
feasible solutions can be compared by replacing one chosen item with another,
you suspect an optimal solution can be transformed to agree with the greedy choice step by step.
Core Idea
Take an arbitrary optimal solution. If it does not use the greedy first choice, modify it so that it does, without making the solution worse. Once the first choice is forced, recurse on the remaining subproblem.
Key Insight
The exchange does not have to preserve the exact same structure. It only has to preserve feasibility and total quality. This is why greedy proofs often feel easier after the right invariant is named: earliest finish time, smallest weight, most urgent deadline, and so on.
Worked Problem
Problem.
Given intervals \([l_i, r_i)\), choose as many pairwise non-overlapping intervals as possible.
Greedy rule.
Sort by increasing right endpoint and always take the first interval that starts after the previously chosen one ends.
Why the rule is safe.
Let \(g\) be the interval with the smallest ending time. Consider any optimal solution and let \(o\) be its first chosen interval. Since \(r_g \le r_o\), replacing \(o\) with \(g\) cannot block any later interval that used to fit after \(o\). So there exists an optimal solution that starts with \(g\).
Problem Pattern
This proof shape also appears in:
interval scheduling,
Huffman-style merging arguments,
choosing edges in MST proofs,
deadline scheduling and certain matroid-style problems.
Correctness Intuition
The exchange argument is constructive: it tells you how to repair any optimal solution that disagrees with the greedy choice. After enough repairs, you get an optimal solution that matches the greedy algorithm entirely.
Complexity Analysis
The proof technique itself has no complexity. In the interval-scheduling example, sorting dominates and the algorithm runs in \(O(n \log n)\).
Implementation
The code below is the canonical interval-scheduling example. The algorithm is short, but the note matters because the proof pattern transfers to many other greedy routines.
Common Pitfalls
Confusing a convincing example with an actual exchange proof.
Replacing one object with another without checking that all future feasibility constraints remain valid.
Using an exchange argument when the problem lacks enough structure; sometimes DP is the real answer.
Variants / Extensions
Stay-ahead proofs, where the greedy partial solution is never behind any optimal partial solution.
Cut and cycle properties for graph greedy algorithms.
Matroid arguments, which formalize when greedy works globally.
Practice Problems
Select the maximum number of non-overlapping intervals.
Prove the correctness of Kruskal's algorithm.
Scheduling tasks with a greedy order and a swap-based proof.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Interval {
long long l;
long long r;
};
vector<Interval> maximum_non_overlapping_intervals(vector<Interval> intervals) {
sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
if (a.r != b.r) return a.r < b.r;
return a.l < b.l;
});
vector<Interval> chosen;
long long current_end = numeric_limits<long long>::lowest();
for (const Interval& interval : intervals) {
if (interval.l >= current_end) {
chosen.push_back(interval);
current_end = interval.r;
}
}
return chosen;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.