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 with proofs is on the syllabus but has not had its own lesson yet. This page is a preview, so read §2.3 carefully.

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. 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\).

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.

6. 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

---

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 solution, mistakes) is ours.