Sorting & Greedy

In one sentence

Sort the data by the right key, then make the choice that looks best right now. Before trusting it, prove that no better plan could beat it.

Where we are

Custom sorting was on our slides (16 Jan) and we use it constantly. Greedy got its own lesson on 27 Sep 2026 (Set 12): §5 has the three problems from that class, and §5.4 is the homework problem we fixed on 4 and 11 Oct. §1–§4 (Save More Mice) were not covered in class, so read them yourself, especially the exchange argument in §2.3.

1. What problem does it solve?

Example — 1593C · Save More Mice (1 · E, 2-BinarySearch · A, rating 1000)

On a number line, a cat is at \(0\), a hole is at \(n\), and \(k\) mice are at positions \(x_1, \dots, x_k\) with \(0 < x_i < n\).

Every second: first you choose one mouse and it moves \(1\) to the right (if it reaches \(n\) it hides and is safe); then the cat moves \(1\) to the right and eats every mouse at its new position.

What is the largest number of mice you can save?

Limits: \(t \le 10^4\), \(n \le 10^9\), \(k \le 4 \cdot 10^5\), sum of \(k \le 4 \cdot 10^5\).

Input                    Output
3
10 6
8 7 5 4 9 4              3
2 8
1 1 1 1 1 1 1 1          1
12 11
1 2 3 4 5 6 7 8 9 10 11  4

A mouse at \(x\) needs \(d = n - x\) moves to reach the hole: its distance. In the first test the distances are \(2, 3, 5, 6, 1, 6\).

Which mice should get your moves? Intuition says the ones closest to the hole: they need the fewest seconds, so the cat advances the least while they escape. We sort by distance and save mice in that order while we can. The rest of this page makes that precise and proves it.

2. The math

2.1 How Python compares things

sort() puts smaller values first. For tuples and lists, it compares the first items; only if they are equal does it look at the second, and so on:

(1, 5) < (2, 3)      because 1 < 2
(1, 4) < (1, 5)      first items tie, 4 < 5

key=lambda x: ... tells sort what to compare instead of the whole item. Two useful facts:

• Descending order for numbers: use key=lambda x: -value, or reverse=True.
• Python's sort is stable: items with equal keys keep their current order. So sorting by a second key and then by the main key gives a two-level sort.

Cost: \(O(n \log n)\). For \(k = 4 \cdot 10^5\) that is fast.

2.2 A rule every saved group must follow

Claim 1. If a group of mice is saved, their distances add up to less than \(n\).

Proof. Every second exactly one mouse moves, so the saved mice need \(D = \sum d\) seconds of moves in total, and the last one hides at some second \(T \ge D\). Just before that final move, \(T - 1 \ge D - 1\) seconds have passed, so the cat stands at position \(\ge D - 1\). The mouse is at \(n - 1\) and has not been eaten, so the cat must be strictly behind it: \(D - 1 < n - 1\), which means \(D < n\). \(\blacksquare\)

2.3 The closest mice always work

Sort distances increasingly: \(d_1 \le d_2 \le \dots \le d_k\).

Claim 2. If \(d_1 + \dots + d_m < n\), then saving the \(m\) closest mice, one at a time, closest first, works.

Proof. Before we start mouse \(j\), exactly \(T = d_1 + \dots + d_{j-1}\) seconds have passed, so the cat is at \(T\). Mouse \(j\) is at \(n - d_j\). It is ahead of the cat when

\[ T < n - d_j \iff d_1 + \dots + d_j < n, \]

which holds because it is a prefix of a sum that is \(< n\). While mouse \(j\) moves, it and the cat both advance by \(1\) per second, so the gap never shrinks and it reaches the hole. Mice we have not started yet are further right than the cat for the same reason. \(\blacksquare\)

Why this is optimal (exchange argument). Suppose some strategy saves \(m\) mice. By Claim 1, their distances sum to less than \(n\). The \(m\) smallest distances sum to at most that much, so they are also \(< n\), and by Claim 2 the \(m\) closest mice can be saved. So swapping any saved group for the closest group never loses. The answer is the largest \(m\) with \(d_1 + \dots + d_m < n\).

Check the first test: sorted distances \(1, 2, 3, 5, 6, 6\). Prefix sums \(1, 3, 6, 11, \dots\). The first three are \(< 10\), the fourth is not. Answer \(3\). ✓

2.4 The general pattern

Most greedy proofs look like §2.3: take any optimal answer, swap in the greedy choice, and show it is no worse. And before proving anything, test the rule on 3–4 tiny cases. Most wrong greedy ideas break there.

3. Template

From our slides (USACO Algorithm — From Bronze to Silver, 16 Jan):

# Data: [Start, End]
intervals = [[1, 5], [2, 3], [1, 4], [5, 6]]

# 1. Standard Sort (First element, then second)
intervals.sort()
# Result: [[1, 4], [1, 5], [2, 3], [5, 6]]

# 2. Sort by End Time (Common for Greedy)
# Use "key=lambda x: ..." to pick what to compare
intervals.sort(key=lambda x: x[1])
# Result: [[2, 3], [1, 4], [1, 5], [5, 6]]

# 3. Sort by Length (Descending)
# (End - Start). Use negative sign "-" for descending.
intervals.sort(key=lambda x: -(x[1] - x[0]))

After step 3 the list is [[1, 5], [1, 4], [2, 3], [5, 6]]: lengths \(4, 3, 1, 1\). The two length-1 intervals keep their order from step 2, because the sort is stable.

4. Worked solution — Save More Mice

Sort the positions by distance to the hole, using a key as in the template. Then add distances while the total stays below \(n\).

import sys

input = sys.stdin.readline


def solve():
    n, k = map(int, input().split())
    x = list(map(int, input().split()))

    x.sort(key=lambda p: n - p)

    used = 0
    saved = 0
    for p in x:
        d = n - p
        if used + d < n:
            used += d
            saved += 1
        else:
            break

    print(saved)


t = int(input())
for _ in range(t):
    solve()

Trace on the first test (\(n = 10\)):

position	distance	used + d	\(< 10\)?	saved
9	1	1	yes	1
8	2	3	yes	2
7	3	6	yes	3
5	5	11	no, stop	3

5. Lesson of 27 Sep — three more greedy problems

All three follow the same two steps: decide what to sort by, then argue that the greedy choice is never worse.

5.1 1539C · Stable Groups (12 · B, rating 1200)

Problem

\(n\) students have levels \(a_1, \dots, a_n\) (up to \(10^{18}\)). A group is stable if, after sorting its levels, neighbours differ by at most \(x\). You may add at most \(k\) new students with any levels you like. What is the smallest number of stable groups that covers everyone?

Sort first. The input is not sorted. The first sample happens to be, the second is not.

After sorting, every gap \(g = a_i - a_{i-1} > x\) splits a group. With no extra students the answer is \((\text{number of such gaps}) + 1\).

To close a gap \(g\), the new students must cut it into pieces of length \(\le x\). That takes \(\lceil g / x \rceil\) pieces, so \(\lceil g / x \rceil - 1\) students. The \(-1\) is there because each new student is the right end of one piece and the left end of the next.

gap \(g\) (\(x = 3\))	pieces	students
4	2	1
6	2	1
7	3	2

Greedy: every closed gap saves exactly one group, whatever it costs. So close the cheapest gaps first: sort the costs and spend \(k\) while you can.

The code we wrote in class:

def solve():
    n, k, x = map(int, input().split())
    a = [int(z) for z in input().split()]

    a.sort()

    g = 1
    u = []
    for i in range(1, n):
        d = a[i] - a[i - 1]
        if d > x:
            u.append((d + x - 1) // x - 1)
            g += 1

    u.sort()
    for ui in u:
        if ui <= k:
            k -= ui
            g -= 1
        else:
            break

    print(g)

(d + x - 1) // x is \(\lceil d / x \rceil\) without importing math. See Numbers.

It was right, and still got TLE

This code is \(O(n \log n)\) with \(n = 2 \cdot 10^5\), which should take well under a second. It got TLE on PyPy 3 (32-bit) and about 200 ms on PyPy 3.10 (64-bit), with not one character changed. The reason is that \(a_i\) goes up to \(10^{18}\). See Complexity §2.8.

5.2 1729D · Friends and the Restaurant (12 · C, rating 1200)

Problem

Friend \(i\) wants to spend \(x_i\) and has \(y_i\). Split some of the friends into groups of at least two, each friend in at most one group, so that in every group \(\sum y \ge \sum x\). Maximise the number of groups.

Only the surplus matters. Replace each friend by \(d_i = y_i - x_i\). A group is fine when \(\sum d \ge 0\).

Groups of two are enough. Take a fine group of three or more people and remove its member with the smallest \(d\). If that \(d\) is negative, the sum goes up. If it is \(\ge 0\), everyone left is \(\ge 0\) anyway. Either way the group is still fine, and the removed person is free for another group. So never build a group bigger than two.

Pairing with two pointers. Sort \(d\). l points at the poorest friend, r at the richest.

• \(d_l + d_r \ge 0\): pair them. The richest can carry the poorest.
• \(d_l + d_r < 0\): even the richest cannot carry \(d_l\), so nobody can. Drop the poorest (l += 1). Adding a third, richer person does not help, as shown above.
• Stop when l == r: one person cannot form a group.

    d = [yi - xi for xi, yi in zip(x, y)]
    d.sort()

    l = 0
    r = n - 1
    ans = 0
    while l < r:
        if d[l] + d[r] >= 0:
            ans += 1
            l += 1
            r -= 1
        else:
            l += 1

    print(ans)

5.3 1561C · Deep Down Below (12 · D, rating 1300) — homework

Problem

There are \(n\) caves. Cave \(i\) has \(k_i\) monsters with armour \(a_{i,1}, \dots, a_{i,k_i}\), which must be fought in this order. The hero beats a monster only if power \(>\) armour (strictly), and then gains \(+1\) power. The hero clears the caves one by one, in any order. What is the smallest starting power that clears every cave?

What we worked out in class:

1. One cave. The monsters cannot be reordered, so walk through them and ask what starting power each one requires. In [12, 11], beating 12 needs power \(13\). After that the hero has \(14 > 11\). So this cave needs \(13\). A single monster with armour \(42\) needs \(43\).
2. Several caves. Call a cave's requirement its need. Enter the cave with the smallest need first. Its monsters only add power, which makes the later caves easier.
3. Binary search on the answer. If starting power \(p\) works, then \(p + 1\) also works. So the results look like ✗ ✗ ✗ ✓ ✓ ✓, and we binary search for the first ✓. To check one \(p\), go through the caves in order of need and keep adding \(k_i\) to the power.

Writing the code is your homework. Use the binary search template for step 3.

5.4 1443C · The Delivery Dilemma (12 · E, rating 1400) — lessons of 4 and 11 Oct

Problem

Petya orders \(n\) dishes. Dish \(i\) can come by courier, which takes \(a_i\) minutes, and all couriers travel at the same time. Or Petya fetches it himself in \(b_i\) minutes, and he fetches his dishes one after another. What is the earliest time at which all dishes are at home?

What to sort by. If Petya fetches a dish whose courier takes \(a\) minutes, he should also fetch every dish with a slower courier, otherwise that slower courier still decides the waiting time. So sort by \(a\): Petya fetches a suffix of the sorted list and couriers bring the rest.

Try every cut. Go from the slowest courier down. Keep walk, the sum of \(b\) over the dishes Petya fetches. The slowest remaining courier is simply the previous element of the sorted list, so the time for this cut is \(\max(a_{i-1}, \text{walk})\).

def solve():
    n = int(input())
    a = [int(z) for z in input().split()]
    b = [int(z) for z in input().split()]

    dishes = sorted(zip(a, b))

    ans = dishes[-1][0]          # every dish comes by courier
    walk = 0
    for i in range(n - 1, -1, -1):
        walk += dishes[i][1]     # Petya fetches dish i too
        courier = dishes[i - 1][0] if i > 0 else 0
        ans = min(ans, max(courier, walk))

    print(ans)

The idea was right, and it still got TLE

Your version had this idea and looked like one loop, so you counted it as \(O(n)\). But inside the loop it called time.copy() and max(time). Each of those walks the whole list, so the loop was \(O(n^2)\): with \(n = 2 \cdot 10^5\) that is \(4 \cdot 10^{10}\) steps. Switching compilers cannot fix that.

The fix uses the sorting twice. The list is in increasing order, and we only remove elements from the end, so the largest remaining element is always the last one. max(...) over the list becomes one index, \(O(1)\).

When you get TLE, go through the loop line by line and write the cost next to each line. The table is in Complexity §2.5.

6. Common mistakes

<= instead of <

Claim 1 gives a strict inequality. In the second test (\(n = 2\), all mice at \(1\), distance \(1\)), <= would save two mice, but the cat reaches \(1\) after the first second and eats the rest. The answer is \(1\).

Assuming the input is sorted

In Stable Groups the first sample happens to be sorted, and the second is not. If the problem does not say sorted, sort it yourself.

Submitting without running every sample

WA on test 1 means you failed the first sample, and Codeforces shows you that test. Run all samples locally before you submit. Each wrong submission costs points in a contest.

Trusting a greedy rule without a counterexample hunt

Most wrong greedy ideas fail on 3–4 items. Try small cases by hand, or with a tiny brute force, first.

sorted(x) vs x.sort()

x.sort() changes x and returns None. x = x.sort() makes x equal to None. Use x.sort() or x = sorted(x).

Descending by a string key with a minus sign

- only works on numbers. For strings, use reverse=True, or sort twice using stability.

Sorting inside a loop

Each sort is \(O(n \log n)\). Sort once before the loop.

7. Practice

Problem	Set	Rating	Idea
1593C · Save More Mice	1 · E, 2-BinarySearch · A	1000	this page
1791E · Negatives and Positives	1 · D, 4-Misc · G	1100	only the parity of negatives matters
1676E · Eating Queries	4-Misc · B	1100	sort descending: eat the biggest candies first
1133C · Balanced Team	3-TwoPointers · C	1200	sort first, then a window
276C · Little Girl and Maximum Sum	10-prefixsum · F/G	1500	sort values and query counts, match largest with largest
2126C · I Will Definitely Make It	12 · A	1100	sort the towers and climb step by step
1539C · Stable Groups	12 · B	1200	§5.1
1729D · Friends and the Restaurant	12 · C	1200	§5.2
1561C · Deep Down Below	12 · D	1300	§5.3, homework
1443C · The Delivery Dilemma	12 · E	1400	§5.4
2014D · Robert Hood and Mrs Hood	12 · F	1400	each job adds 1 to a range of start days: Difference Array §4
2046B · Move Back at a Cost	12 · G	1600	move a number back if something smaller is to its right; each number moves at most once

---

Credits & licenses

• Section structure follows USACO Guide — Introduction to Sorting by Darren Yao, Benjamin Qi, Allen Li and Andrew Wang, licensed CC BY-NC-SA 4.0.
• The template in §3 is from our slides. Everything else (the two claims, the exchange argument, worked solutions, the lesson problems in §5, mistakes) is ours.