Skip to content

Greedy

In one sentence

A greedy algorithm makes the choice that looks best right now and never takes it back. It is only correct when you can argue that some best answer agrees with that choice, so every greedy needs a short proof.

Where this comes from

Greedy was our seventh problem set, 7-Greedy, assigned on 10 May and worked through in May. There is no separate lesson note, so this page is written from scratch around that set and the greedy proofs we met in AIO.

1. What problem does it solve?

Example — 2193B · Reverse a Permutation (7-Greedy · D, rating 800)

You are given a permutation \(p\) of \(1 \dots n\). Choose exactly one segment \([l, r]\) and reverse it. Output the lexicographically largest permutation you can get.

Limits: \(t \le 10^4\), \(n \le 2\cdot10^5\), sum of \(n \le 2\cdot10^5\).

Input        Output
4
4
3 2 1 4      4 1 2 3
3
3 1 2        3 2 1
4
4 3 2 1      4 3 2 1
2
2 1          2 1

Lexicographic order is decided by the first difference. So we should make position \(1\) as large as possible, then position \(2\), and so on. Trying all \(O(n^2)\) segments and comparing \(O(n)\) arrays is \(O(n^3)\); the greedy idea gives \(O(n)\).

2. The math

2.1 The greedy choice

The best possible array is \(n, n-1, \dots, 1\). Let \(i\) be the first position where \(p_i \ne n - i + 1\) (1-indexed).

  • If there is no such \(i\), \(p\) is already the best; reverse a single element (\(l = r\)) and print \(p\).
  • Otherwise, the value \(v = n - i + 1\) sits at some position \(j > i\) (it cannot be earlier, because positions \(1 \dots i-1\) hold \(n, \dots, v+1\)). Reverse \([i, j]\): this brings \(v\) to position \(i\).

2.2 Why it is optimal

Compare our result with any other reversal \([l, r]\).

  1. Positions before \(i\) cannot improve. They already hold the largest possible values.
  2. Starting before \(i\) only hurts. If \(l < i\), position \(l\) receives \(p_r\). All values bigger than or equal to \(p_l = n - l + 1\) are at positions \(\le l\), so \(p_r < p_l\) unless \(r = l\). The array gets smaller at position \(l\).
  3. Position \(i\) can be at most \(v\). Every bigger value is already used before \(i\). Our reversal achieves \(v\); a reversal with \(l > i\) leaves \(p_i < v\) in place, and a reversal with \(l = i\) puts \(p_r\) at position \(i\), which equals \(v\) only for \(r = j\).

So every other choice is worse at the first position where it differs, or it is our reversal. This "it agrees with us, or we can show it is worse" pattern is how most greedy proofs go.

2.3 Trace on sample 1

\(n = 4\), \(p = (3, 2, 1, 4)\). Target \((4, 3, 2, 1)\). First mismatch: \(i = 1\) (\(3 \ne 4\)). Value \(4\) is at \(j = 4\). Reverse \([1, 4]\) → \((4, 1, 2, 3)\).

Sample 2: \(p = (3, 1, 2)\), target \((3, 2, 1)\). Position \(1\) matches; \(i = 2\), value \(2\) is at \(j = 3\); reverse \([2, 3]\) → \((3, 2, 1)\).

2.4 Three ways to prove a greedy

Method Idea Where we used it
first difference fix the answer position by position; anything else is worse where it first differs this page
exchange argument take any optimal answer that disagrees with greedy; swap two things to make it agree without getting worse AIO 2024 · Shopping Spree, AIO 2019 · RPS, AIO 2025 · ORAC
stays ahead after every step, greedy has at least as much room / as good a state as any other plan AIO 2022 · TSP, AIO 2021 · Social Distancing

3. Template

There is no single greedy template. The shape that covers most problems in the set is:

1. Decide what "best right now" means (smallest end, largest value, closest to the goal, ...).
2. Usually sort by that key.
3. Scan once, taking the best choice that is still allowed.
4. Before coding: write the 2-3 line proof (§2.4). If you cannot, try a tiny counterexample by hand.

4. Worked solution — Reverse a Permutation

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    // first position (0-indexed) that does not hold n - i
    int i = 0;
    while (i < n && p[i] == n - i) {
        i++;
    }

    if (i < n) {
        int j = i;
        while (p[j] != n - i) {
            j++;
        }
        reverse(p.begin() + i, p.begin() + j + 1);
    }

    for (int k = 0; k < n; k++) {
        cout << p[k] << " ";
    }
    cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

Both while loops together move forward at most \(n\) steps, and reverse is \(O(n)\), so each test is \(O(n)\).

5. Common mistakes

A greedy that \"obviously\" works

Many greedies are wrong. Before submitting, test your rule on 3–4 tiny inputs where you can find the true answer by hand, and look for a case where a worse-looking first step pays off later.

Sorting by the wrong key

"Earliest start" and "earliest end" lead to different algorithms for interval problems; only one is usually right. Say out loud why your key is the right one.

Proving the easy half only

Showing that greedy gives a valid answer is not enough; the proof must show that no other answer is better.

6. Practice

Problem Set Rating Greedy idea
2200A · Eating Game 7-Greedy · A 800 only players with the most dishes can eat last
2218B · The 67th 6-7 Integer Problem 7-Greedy · B 800 —
2194A · Lawn Mower 7-Greedy · C 800 keep one board in every block of \(w\): \(n - \lfloor n/w \rfloor\)
2193B · Reverse a Permutation 7-Greedy · D 800 first difference (this page)
2193C · Replace and Sum 7-Greedy · E 1000 —
2190A · Sorting Game 7-Greedy · F 1200 —
2189A · Table with Numbers 7-Greedy · G 800 —
2189B · The Curse of the Frog 7-Greedy · H 1200 —
2188B · Seats 7-Greedy · I 1000 —
2185B · Prefix Max 7-Greedy · J 800 —
AIO 2022 · TSP AIO 2022 Q3 — sell as little as allowed each day
AIO 2024 · Backpacking AIO 2024 Q4 — buy just enough to reach the next cheaper town
Credits & licenses

Everything on this page (example proof, method table, worked solution, mistakes, practice notes) is ours. Problem statements are summarised; the originals are on Codeforces.