SyntaxPilot
Courses/Competitive Programming/Lesson 14
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 14 of 90

Greedy with exchange-argument proofs

queued

These are the notes for Competitive Programming episode 14. An original problem, Repair Queue, asks in which order one technician should repair phones so that the owners lose as little money as possible. Two natural greedy rules (shortest repair first, biggest loss first) both give the wrong answer. Trying every order is correct but needs n! orders (TLE). A stress test finds a two-phone counterexample, and looking at just two neighbouring jobs gives the exchange argument: swap them, only they change, compare the two costs. That inequality becomes a comparator, and one sort solves the problem in O(n log n). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook: Raju's repair shop

Raju is the only technician at a phone repair shop and repairs one phone at a time. Three phones arrive together: one needs 1 minute (its owner, a delivery rider, loses ₹6 a minute without it), one needs 7 minutes (a student, ₹1 a minute), one needs 9 minutes (a shopkeeper, ₹7 a minute). In what order should he repair them so the total money lost is smallest?

The problem: Repair Queue

Problem N · Repair Queue (written for this course). There are n phones and one technician. Phone i needs t[i] minutes of work, and its owner loses w[i] rupees for every minute until it is ready. Let C[i] be the minute phone i is finished. Choose the order of repairs that minimises

Σ w[i] · C[i]

1 ≤ n ≤ 2·10^5, 1 ≤ t[i], w[i] ≤ 10^4. Print the minimum total loss.

Sample input Sample output
3
1 6
7 1
9 7
93

Best order: the 1-minute phone (finishes at 1, costs 6), then the 9-minute phone (finishes at 10, costs 70), then the 7-minute phone (finishes at 17, costs 17): 6 + 70 + 17 = 93.

Greedy: what it is

A greedy algorithm builds the answer step by step, always taking the choice that looks best right now by one simple rule, and never goes back to change it. Greedy solutions are short and fast, but a greedy rule is only a guess until it is proved.

Guess 1: shortest repair first (Wrong Answer)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
    ll T = 0, s = 0;
    for (int i : ord) {
        T += t[i];
        s += w[i] * T;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> t(n), w(n);
    for (int i = 0; i < n; i++) cin >> t[i] >> w[i];
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return t[a] < t[b];
    });
    cout << cost(ord, t, w) << "\n";
    return 0;
}

Output on the sample:

133

Guess 2: biggest loss first (Wrong Answer)

Change the comparator to return w[a] > w[b];. Output on the sample:

140

Shortest-first ignores how much each owner loses; biggest-loss-first ignores how long each repair blocks everyone behind it.

Brute force: try every order (correct, but TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
    ll T = 0, s = 0;
    for (int i : ord) {
        T += t[i];
        s += w[i] * T;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> t(n), w(n);
    for (int i = 0; i < n; i++) cin >> t[i] >> w[i];
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    ll best = LLONG_MAX;
    do {
        best = min(best, cost(ord, t, w));
    } while (next_permutation(ord.begin(), ord.end()));
    cout << best << "\n";
    return 0;
}

next_permutation steps through every ordering of the phone numbers (they start sorted, 0 1 2 …, which is what iota gives). On the sample it prints 93. On 13 phones there are 13! = 6,227,020,800 orders: Time Limit Exceeded in the SyntaxPilot compiler (run locally it needed more than 20 seconds and printed 1069).

13-phone input:

13
5 2
3 9
8 1
2 2
7 6
4 4
9 3
1 8
6 5
3 3
8 7
2 9
5 1

Stress test: find a tiny counterexample

The brute force is slow but always right, so it can act as a judge. A stress test (episode 5) generates random small inputs, runs the brute force and the candidate solution, and stops at the first difference.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
    ll T = 0, s = 0;
    for (int i : ord) {
        T += t[i];
        s += w[i] * T;
    }
    return s;
}

int main() {
    mt19937 rng(1);
    for (int it = 1; it <= 1000; it++) {
        int n = rng() % 6 + 1;
        vector<ll> t(n), w(n);
        for (int i = 0; i < n; i++) {
            t[i] = rng() % 10 + 1;
            w[i] = rng() % 10 + 1;
        }
        vector<int> o(n);
        iota(o.begin(), o.end(), 0);
        ll best = LLONG_MAX;
        do best = min(best, cost(o, t, w));
        while (next_permutation(o.begin(), o.end()));
        sort(o.begin(), o.end(), [&](int a, int b) {
            return t[a] < t[b];
        });
        ll g = cost(o, t, w);
        if (best != g) {
            cout << "test " << it << " FAILS\n";
            for (int i = 0; i < n; i++)
                cout << t[i] << " " << w[i] << "\n";
            cout << best << " vs " << g << "\n";
            return 0;
        }
    }
    cout << "all 1000 tests passed\n";
    return 0;
}

Real output:

test 1 FAILS
10 5
9 4
126 vs 131

Two phones are enough to break shortest-first: the 9-minute phone (weight 4) before the 10-minute phone (weight 5) costs 36 + 95 = 131; the other order costs 50 + 76 = 126.

The key observation: swap two neighbours (the exchange argument)

Take two phones i and j that are next to each other in the order. Swapping them does not change anyone else's finish time: everything before them is the same, and the two together take t[i] + t[j] minutes either way, so everything after them is the same too. Only the two of them change:

Order Extra waiting Extra cost
i then j j waits t[i] extra minutes w[j] · t[i]
j then i i waits t[j] extra minutes w[i] · t[j]

So i should go first exactly when

t[i] · w[j] < t[j] · w[i] (the same as t[i] / w[i] < t[j] / w[j]: minutes of work per rupee of loss, smallest first).

Proof (exchange argument). Take any optimal order. If some pair of neighbours breaks the rule, swap them: by the table above the total does not increase. Each such swap fixes one out-of-order pair, so after finitely many swaps we reach the sorted order, still with the optimal total. Therefore the sorted order is optimal. Ties (equal t·w products) cost the same in either order, so any tie order is fine.

Check on the sample: ratios 1/6 ≈ 0.17, 9/7 ≈ 1.29, 7/1 = 7, so the order is 1-minute, 9-minute, 7-minute phone: exactly the order the brute force found.

Real-life picture: two neighbours in a ticket queue swap places; everyone in front and behind waits exactly as long as before, so only those two people's costs need to be compared.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
    ll T = 0, s = 0;
    for (int i : ord) {
        T += t[i];
        s += w[i] * T;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> t(n), w(n);
    for (int i = 0; i < n; i++) cin >> t[i] >> w[i];
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return t[a] * w[b] < t[b] * w[a];
    });
    cout << cost(ord, t, w) << "\n";
    return 0;
}
Input Output
sample 93
the 13 phones above 1069 (instantly; the brute force agrees)
1
10000 10000 (one phone, maximum values)
100000000
3
2 4
1 2
3 6 (all ratios equal)
50
2
9 4
10 5 (the stress-test counterexample)
126
2·10^5 phones of 10000 10000 2000010000000000000

The stress test with this comparator prints all 1000 tests passed.

Trap: integer division in the comparator (real output)

return t[a] / w[a] < t[b] / w[b];

On the input 2
9 4
10 5 it prints 131 (expected 126): 9/4 and 10/5 are both 2 in integer division, so the sort sees a tie and keeps the wrong order. Cross-multiply instead: t[a] * w[b] < t[b] * w[a] (at most 10^8, exact in long long).

Solutions in C++, Java and Python

C++: the accepted program above.

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in);
        long[] t = new long[n], w = new long[n];
        for (int i = 0; i < n; i++) {
            t[i] = nextInt(in);
            w[i] = nextInt(in);
        }
        Integer[] ord = new Integer[n];
        for (int i = 0; i < n; i++) ord[i] = i;
        Arrays.sort(ord, (a, b) -> Long.compare(t[a] * w[b], t[b] * w[a]));
        long T = 0, s = 0;
        for (int i : ord) {
            T += t[i];
            s += w[i] * T;
        }
        System.out.println(s);
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') {
            r = r * 10 + (b - '0');
            b = in.read();
        }
        return r;
    }
}

Python

import sys
from functools import cmp_to_key

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    t = list(map(int, data[1:2 * n + 1:2]))
    w = list(map(int, data[2:2 * n + 2:2]))

    def cmp(a, b):
        x, y = t[a] * w[b], t[b] * w[a]
        return -1 if x < y else (1 if x > y else 0)

    order = sorted(range(n), key=cmp_to_key(cmp))
    T = s = 0
    for i in order:
        T += t[i]
        s += w[i] * T
    print(s)

main()

All three print 93 on the sample, 1069 on the 13 phones, 50 on the ties input and 2000010000000000000 on 2·10^5 phones of 10000 10000.

Brute force vs optimal

Shortest / biggest first All orders (next_permutation) Exchange-argument sort
Time O(n log n) O(n! · n) O(n log n)
n = 13 instant 6.2·10^9 orders: TLE instant
n = 2·10^5 instant impossible ≈ 3.5·10^6 comparisons
Correct? no (133 / 140) yes yes (proved + stress-tested)
Memory O(n) O(n) O(n)

Common mistakes (and the real messages)

Mistake What you see Why Fix
Sort by t only, or by w only 133 / 140 instead of 93 a rule that feels right, never checked stress test + exchange argument
t[a] / w[a] < t[b] / w[b] 131 instead of 126 integer division: 9/4 = 10/5 = 2 t[a] * w[b] < t[b] * w[a]
t[a] * w[b] <= t[b] * w[a] Segmentation fault (2·10^5 equal phones) <= breaks strict weak ordering; std::sort runs past the array strict <
Total in int -1657102336 (correct: 2000010000000000000) the answer reaches about 2·10^18 long long (up to about 9.2·10^18)

The greedy recipe for contests

  1. Guess a rule (usually "sort by something").
  2. Try to break it: brute force + stress test on tiny inputs. Most wrong greedy ideas die here.
  3. Prove it: swap two neighbours and compare the two costs.
  4. Turn the inequality into a comparator: multiply, don't divide; keep it strict.
  5. If swapping two neighbours changes things far away, the exchange argument doesn't apply, and greedy may be wrong: think dynamic programming.

Mini project: minimise the worst lateness

Each job has a time t[i] and a deadline d[i]; lateness is max(0, C[i] − d[i]). Minimise the largest lateness. Exchange argument: for neighbours i, j with d[i] ≤ d[j], putting i first never makes the worse of the two latenesses bigger, so sort by deadline (earliest deadline first).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<pair<ll, ll>> job(n);   // (deadline, time)
    for (auto& [d, t] : job) cin >> t >> d;
    sort(job.begin(), job.end());
    ll T = 0, worst = 0;
    for (auto [d, t] : job) {
        T += t;
        worst = max(worst, T - d);
    }
    cout << worst << "\n";
    return 0;
}

Input 3 / 3 5 / 2 2 / 4 6 (each line t d) prints 3: deadlines 2, 5, 6 finish at 2, 5, 9, so the worst lateness is 9 − 6 = 3.

Practice

  1. All weights are 1 (minimise Σ C[i]). Which order is best? Prove it.

    Answer Shortest first. With <code>w = 1</code> the rule <code>t[i]·w[j] < t[j]·w[i]</code> becomes <code>t[i] < t[j]</code>. For times 3, 1, 2 the best total is <code>10</code> (1, 2, 3 → finish times 1, 3, 6).

  2. Phone A (t = 4, w = 2) and phone B (t = 3, w = 1). Which first?

    Answer A: 4·1 = 4 < 3·2 = 6. A first costs 8 + 7 = 15; B first costs 3 + 14 = 17.

  3. Why does the comparator use multiplication instead of double division?

    Answer Products of integers are exact (at most 10^8 here). Integer division truncates (<code>9/4 = 2</code>), and doubles can round two different ratios to the same value on bigger inputs.

  4. Why does swapping two neighbours not change the other phones' costs?

    Answer Phones before them are untouched, and the pair together still takes <code>t[i] + t[j]</code> minutes, so every phone after them finishes at the same minute as before.

  5. Stress-test the integer-division comparator: what is the smallest counterexample?

    Answer Two phones whose ratios differ but truncate to the same integer, in the wrong input order, e.g. <code>2</code> / <code>9 4</code> / <code>10 5</code> → 131 instead of 126. (Even <code>2</code> / <code>3 2</code> / <code>2 2</code> fails: 3/2 = 1 = 2/2.)

Quick quiz

Phone A: t = 4, w = 2; phone B: t = 3, w = 1. Which goes first?

A) B: it is shorter · B) A: 4·1 < 3·2 · C) Either: same cost · D) B: 3·2 < 4·1

Answer

B. A goes first iff t[A]·w[B] < t[B]·w[A]: 4 < 6. Total 15 instead of 17.

Interview questions

  1. What is a greedy algorithm? One that builds the answer with a fixed local rule and never revisits a choice.
  2. How do you prove a greedy is correct? Exchange argument: take any optimal solution, swap a pair that disagrees with the greedy, show it's not worse; repeat until it matches the greedy. (The other common style is "greedy stays ahead".)
  3. Weighted completion time on one machine? Sort by t/w ascending (Smith's rule), compared as t[i]·w[j] < t[j]·w[i].
  4. Why must a comparator be strict? std::sort requires a strict weak ordering; <= can make it read past the array and crash.
  5. How do you test a greedy quickly in a contest? A brute force on tiny inputs plus a random stress test.

Glossary

Term Meaning Example
Greedy algorithm Builds the answer step by step with one simple rule, never undoes a choice shortest repair first
Exchange argument Proof: swap two neighbours that break the rule; the answer never gets worse w[j]·t[i] vs w[i]·t[j]
Weight w[i] How much one minute of waiting costs for job i ₹6 per minute
Finish time C[i] The minute job i is done 10 for the 9-minute phone
Weighted completion time Σ w[i] · C[i] 93 on the sample
Counterexample An input where a solution gives the wrong answer 9 4 / 10 5
Stress test Random small inputs, brute force vs fast solution, stop at the first difference mt19937 rng(1)
next_permutation Rearranges a range into the next order; returns false after the last all 3! orders
iota Fills a range with 0, 1, 2, … phone numbers
Comparator A function telling sort whether a goes before b t[a] * w[b] < t[b] * w[a]
Strict weak ordering The rules a comparator must follow; in particular comp(a, a) is false <, never <=
Cross-multiplication Comparing a/b < c/d as a·d < c·b (for positive b, d) t[i]·w[j] < t[j]·w[i]
long long 64-bit integer, up to about 9.2·10^18 the total loss
Segmentation fault The program touched memory it doesn't own and was killed <= comparator

Summary

  • Greedy = one rule, never undo. Shortest-first gave 133, biggest-loss-first 140; the answer is 93.
  • Trying all orders is right but n!: 13 phones already TLE.
  • A stress test found a 2-phone counterexample: 126 vs 131.
  • Exchange argument: swapping neighbours only affects them; i first iff t[i]·w[j] < t[j]·w[i].
  • Sort with that comparator: O(n log n), passes the stress test. Multiply, don't divide; strict <; long long total.

Next episode: constructive problems: build any valid answer.