Sorting by Formula
The Exchange Argument: Your Most Powerful Tool
Here's something that takes a while to click, but once it does, you'll see it everywhere:
~80% of greedy problems reduce to: sort by some formula. The hard part isn't the sorting — it's figuring out which formula. And the way you figure it out is the exchange argument.
The Problem That Demands This
CSES 1630 — Tasks and Deadlines: You have n tasks. Task i has duration \(a_i\) and deadline \(d_i\). You process tasks sequentially, starting at time 0. The reward for task i is \(d_i - f_i\), where \(f_i\) is the time you finish it. Maximize total reward.
The Greedy Choice: Sort tasks by duration ascending. Shorter tasks first means smaller multipliers on larger sums — minimizing total finish time.
Note: you must do ALL tasks. You can't skip any. The only freedom is the order.
Total reward \(= \sum(d_i - f_i) = \sum d_i - \sum f_i\).
\(\sum d_i\) is fixed regardless of order. So maximizing total reward is equivalent to minimizing \(\sum f_i\).
This reframing is crucial. We've turned a maximization problem into a minimization problem on finish times.
What Determines Finish Times?
If the order is task \(\sigma(1), \sigma(2), \ldots, \sigma(n)\), then:
So: $\(\sum f_i = a_{\sigma(1)} \cdot n + a_{\sigma(2)} \cdot (n-1) + a_{\sigma(3)} \cdot (n-2) + \ldots + a_{\sigma(n)} \cdot 1\)$
Each task's duration is multiplied by how many tasks come AFTER it (plus itself). Earlier tasks have larger multipliers.
To minimize this weighted sum, we want small durations to have large multipliers — i.e., small durations go first.
Greedy claim: sort by duration \(a_i\) ascending (shortest task first).
The Exchange Proof
Let's make this rigorous.
Suppose an optimal solution OPT has two adjacent tasks \(i\) and \(j\) where \(a_i > a_j\) but \(i\) comes before \(j\). Let \(t\) be the finish time of everything before these two tasks.
Current order (\(i\) before \(j\)): - Finish time of \(i\): \(t + a_i\) - Finish time of \(j\): \(t + a_i + a_j\) - Contribution to \(\sum f\): \((t + a_i) + (t + a_i + a_j) = 2t + 2a_i + a_j\)
After swapping (\(j\) before \(i\)): - Finish time of \(j\): \(t + a_j\) - Finish time of \(i\): \(t + a_j + a_i\) - Contribution to \(\sum f\): \((t + a_j) + (t + a_j + a_i) = 2t + a_i + 2a_j\)
Difference:
Since we assumed \(a_i > a_j\), this difference is positive. The current order contributes more to \(\sum f\) than the swapped order. Swapping strictly reduces \(\sum f\).
This means: if OPT has any adjacent pair in the "wrong" order (longer before shorter), we can swap them to get a strictly better solution — contradicting OPT's optimality. Therefore, the optimal order has no wrongly-ordered adjacent pairs. That's exactly the sorted-by-duration order.
The exchange argument is complete.
Tracing the Formula
Example: n=3 tasks: (duration=3, deadline=5), (duration=1, deadline=3), (duration=2, deadline=8).
Sort by duration ascending: order is (1,3), (2,8), (3,5).
| Task | \(a_i\) | \(d_i\) | Finish time \(f_i\) | Reward \(d_i - f_i\) |
|---|---|---|---|---|
| (1,3) | 1 | 3 | 1 | 3-1=2 |
| (2,8) | 2 | 8 | 1+2=3 | 8-3=5 |
| (3,5) | 3 | 5 | 1+2+3=6 | 5-6=-1 |
Total reward: 2 + 5 + (-1) = 6.
Alternative order — sorted by deadline: (1,3), (3,5), (2,8).
| Task | \(a_i\) | \(d_i\) | Finish time \(f_i\) | Reward \(d_i - f_i\) |
|---|---|---|---|---|
| (1,3) | 1 | 3 | 1 | 2 |
| (3,5) | 3 | 5 | 4 | 1 |
| (2,8) | 2 | 8 | 6 | 2 |
Total reward: 2 + 1 + 2 = 5. Worse.
Worst order — duration descending: (3,5), (2,8), (1,3).
| Task | \(a_i\) | \(d_i\) | Finish time \(f_i\) | Reward |
|---|---|---|---|---|
| (3,5) | 3 | 5 | 3 | 2 |
| (2,8) | 2 | 8 | 5 | 3 |
| (1,3) | 1 | 3 | 6 | -3 |
Total: 2 + 3 + (-3) = 2. Much worse.
The greedy (shortest first) is clearly best here.
Example 2: ABC131D — Megalomania (Earliest Deadline First)
Problem: N jobs. Job i takes \(A_i\) time units and has deadline \(B_i\). Process one job at a time. Can all jobs be completed on time?
A job is on time if its finish time \(\leq B_i\).
Greedy claim: sort by deadline \(B_i\) ascending (Earliest Deadline First — EDF).
Exchange proof: Suppose job \(j\) (later deadline \(B_j > B_i\)) is scheduled before job \(i\) (earlier deadline \(B_i\)). The current order starts job \(i\) at time \(t + A_j\) (after job j), finishing at \(t + A_j + A_i\).
Swapping (\(i\) before \(j\)): - Job \(i\) finishes at \(t + A_i\). Since \(t + A_i < t + A_j + A_i\), it's easier to satisfy \(i\)'s deadline. - Job \(j\) finishes at \(t + A_i + A_j\) — the same total time. But \(B_j > B_i\), so \(j\) has more slack anyway.
The swap makes \(i\)'s situation easier (earlier finish) and \(j\)'s situation no worse (same finish time, more slack). If the original order was feasible, the swapped order is also feasible.
So EDF is optimal for feasibility: if any ordering works, EDF works.
Implementation:
sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
});
long long time = 0;
for (const auto& [dur, deadline] : jobs) {
time += dur;
if (time > deadline) { cout << "No\n"; return 0; }
}
cout << "Yes\n";
Example 3: CF545D — Queue
Problem: N people in a queue. Person i needs \(t_i\) time to serve. They're disappointed if their wait exceeds \(t_i\). Find the maximum number of non-disappointed people by reordering.
Key insight: person in position \(k\) has wait time = sum of service times of everyone before them: \(t_{\sigma(1)} + \ldots + t_{\sigma(k-1)}\). They're happy iff this wait \(\leq t_{\sigma(k)}\).
Greedy: sort by \(t_i\) ascending. Serve fastest people first — they have short waits (since less is before them) and are hardest to satisfy. Exchange argument: swapping a faster person before a slower one reduces the faster person's wait (good, since they have less tolerance) and increases the slower person's wait (they can tolerate more).
Example 4: Fractional Knapsack — Sorting by Density
Problem. \(N\) items, each with weight \(w_i\) and value \(v_i\). Knapsack capacity \(W\). You can take fractions of items. Maximize total value.
Greedy claim: sort by value-to-weight ratio \(v_i / w_i\) descending. Take items greedily until the knapsack is full.
Exchange proof: Suppose item \(i\) (ratio \(r_i\)) is taken before item \(j\) (ratio \(r_j\)) with \(r_i < r_j\). Consider swapping a unit of weight from \(i\) to \(j\). The value change is \(r_j - r_i > 0\) — strictly better. So higher-ratio items must come first.
Why this is the gold standard: Fractional Knapsack is the purest exchange argument problem. The sort key (\(v_i / w_i\)) falls directly from comparing adjacent items. It also illustrates why the integer knapsack is hard — you can't take fractions, so the exchange argument breaks (you can't swap "a unit of weight" when items are indivisible).
auto ratioCompare = [&](int indexA, int indexB) {
return (long long)values[indexA] * weights[indexB] > (long long)values[indexB] * weights[indexA];
};
vector<int> itemIndices(numItems);
iota(itemIndices.begin(), itemIndices.end(), 0);
sort(itemIndices.begin(), itemIndices.end(), ratioCompare);
double totalValue = 0.0;
int remainingCapacity = knapsackCapacity;
for (int idx : itemIndices) {
if (weights[idx] <= remainingCapacity) {
totalValue += values[idx];
remainingCapacity -= weights[idx];
} else {
totalValue += (double)values[idx] * remainingCapacity / weights[idx];
break;
}
}
Note: We compare ratios using cross-multiplication (\(v_i \times w_j > v_j \times w_i\)) to avoid floating-point division in the comparator. The actual value computation uses floating point since we take fractions.
Example 5: UVa 11389 — The Bus Driver Problem
Problem: N drivers, N morning routes (durations \(m_i\)), N afternoon routes (durations \(a_i\)). Assign each driver one morning + one afternoon route. If total > \(d\), overtime = total - d. Minimize total overtime.
Greedy: sort morning routes descending, afternoon routes ascending. Pair them.
Why? The rearrangement inequality: to minimize \(\sum \max(m_i + a_{\pi(i)} - d,\; 0)\), pair the largest \(m_i\) with the smallest \(a_j\). This minimizes the maximum pair sums, spreading overtime evenly and minimizing its total.
Exchange proof: If morning route \(m_p > m_q\) is paired with afternoon \(a_x < a_y\) (and \(m_q\) paired with \(a_y\)), then: - Current total from these pairs: \(\max(m_p + a_x - d, 0) + \max(m_q + a_y - d, 0)\) - After swap: \(\max(m_p + a_y - d, 0) + \max(m_q + a_x - d, 0)\)
Since \(m_p > m_q\) and \(a_y > a_x\), the first (current) assignment gives smaller individual sums. The pair (big, small) and (small, big) always gives smaller total overtime than (big, big) and (small, small) — a direct consequence of convexity.
The General Pattern
Every problem in this lesson follows the same flow:
- Reframe: find what you're really optimizing (often sum of finish times, total overtime, etc.)
- Ask: which pair of adjacent elements might be "out of order"?
- Compute: cost with (A before B) vs (B before A)
- Compare: find the condition under which (A before B) is better
- That condition is your sort key
| Problem | Sort by | Why |
|---|---|---|
| Tasks & Deadlines | duration \(a_i\) ascending | shorter tasks multiply fewer terms |
| Megalomania | deadline \(B_i\) ascending (EDF) | satisfying tight deadlines first is always safe |
| Queue | service time \(t_i\) ascending | fast people have tighter constraints |
| Fractional Knapsack | ratio \(v_i/w_i\) descending | higher-density items yield more value per unit weight |
| Bus Driver | (morning desc, afternoon asc) | minimize paired sums via rearrangement |
The Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<pair<int, int>> tasks(n);
long long totalDeadlines = 0;
for (int i = 0; i < n; i++) {
cin >> tasks[i].first >> tasks[i].second;
totalDeadlines += tasks[i].second;
}
sort(tasks.begin(), tasks.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first;
});
long long currentFinishTime = 0;
long long totalFinishTimes = 0;
for (const auto& task : tasks) {
currentFinishTime += task.first;
totalFinishTimes += currentFinishTime;
}
cout << totalDeadlines - totalFinishTimes << "\n";
return 0;
}
The explicit lambda return a.first < b.first makes the greedy choice visible — we're sorting by duration ascending. No hidden behavior.
Try It
Fill in the TODO (add the sorting lambda).
For the second case, trace manually: - Sorted by duration ascending: (2,10), (5,3) - Sum of deadlines: 10 + 3 = 13 - Sum of finish times: 2 + (2+5) = 2 + 7 = 9 - Answer = 13 - 9 = 4
Challenge: What if all deadlines are very large (all rewards positive regardless of order)? Does sorting by duration still matter? What if all durations are equal?
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES — Tasks and Deadlines | cses.fi/problemset/task/1630 | Medium |
| ABC131D — Megalomania | atcoder.jp/contests/abc131/tasks/abc131_d | 400pts |
| CF545D — Queue | codeforces.com/problemset/problem/545/D | 1300 |
| UVa 11389 — The Bus Driver Problem | onlinejudge.org | Medium |
| UVa 11157 — Dynamic Frog | onlinejudge.org | Medium |