Sort, Then Place or Pair

Many greedy problems become obvious once the input is sorted by the right key. Sorting guarantees where the extremes are (the smallest on the left, the largest on the right), so you can pair them, spend from one end and gain from the other, or place items in an order that never needs fixing later. The skill is picking the key and justifying the choice.

The idea#

After sorting, certain positions are guaranteed to hold extremes. That lets you argue about the best choice without trying them all.

Pairing: the heaviest item is the hardest to place. If it can share with anything, it can share with the lightest; if it can't share with the lightest, it can't share with anyone and goes alone.
Placing: process items in an order where each placement can't be disturbed by the ones after it. If later items are invisible to the ones already placed, no placement ever needs fixing.

The proof question is always the same: "if you sort and pick this way, can anything else be better?"

How to spot it#

These signals in a question point to a sort-first greedy.

"Pair up", "groups of two", "boats with at most two people", "split into two teams".
"Maximize the sum of minimums", "spend the cheapest, gain from the most expensive".
An ordering condition with a count, like "exactly k taller people in front".
n up to $10^5$ , which allows $O(n \log n)$ for the sort.

Template#

Here is the pairing shape from above: sort, then point at both ends. The item at the hard end always leaves; the easy end leaves only when a pair forms.

sort items
i = 0, j = last index
count = 0
while i <= j:
    if items[i] and items[j] can share:
        i += 1                # the easy end joins the hard end
    j -= 1                    # the hard end always leaves now
    count += 1
return count

The placing shape#

The second shape sorts so that each new item can't disturb anything placed before it. Then each item goes straight to its final spot.

sort items so later items can't affect earlier ones
result = empty list
for each item in sorted order:
    put item at the position its own rule names
return result

Sorting costs $O(n \log n)$ . A list insert costs $O(n)$ , so the placing shape can reach $O(n^2)$ in total.

Pitfalls#

These mistakes cause the most wrong answers.

Sorting in the direction that lets later items disturb earlier ones. Then each insertion shifts counts you already fixed.
Moving the hard end only when a pair forms. The hardest item must leave every step, alone if needed. That is what keeps the loop correct.
Returning the final score when trades can lose points (as in Bag of Tokens). Track the best score seen.
Picking the sort key by intuition alone. Check it against a small counterexample.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Boats to Save People

Sort, then try to pair the lightest with the heaviest. If they don't fit within limit, the heaviest rides alone, because no lighter partner exists.

Hint: Queue Reconstruction by Height

Sort by height descending, and by k ascending for ties. Insert each person at index k. Everyone already placed is at least as tall, so index k is exactly right, and shorter people inserted later don't change anyone's count.

Hint: Array Partition

Sort and pair neighbors. Each pair's minimum is "wasted" against its partner, and neighbors waste the least. The answer is the sum of every other element of the sorted list, starting at index 0.

Hint: Bag of Tokens

Sort the tokens. Play the cheapest face up to gain a point for the least power. When you can't, play the most expensive face down for the most power per point. Return the best score seen, since the last trade might not help.

Hint: Two City Scheduling

Sort people by cost_a - cost_b. The first half saves the most by going to city A, so send them there and the rest to city B.

Hint: Hand of Straights

The smallest remaining card must start a group, since nothing smaller can come before it. Repeatedly take it and use one each of card .. card + size - 1. If any is missing, the answer is no.

Hint: Assign Cookies

Sort both lists. Walk the cookies from smallest, and give each one to the least greedy child it satisfies. A cookie too small for the current child is too small for every child after them.

Key takeaways#

Sorting puts extremes at known positions, which is what makes the greedy provable.
Pair the extremes: if the largest can't pair with the smallest, it can't pair at all.
Place items in an order that later placements can't disturb.
Always ask: "if you sort and pick this way, can anything else be better?"

Core idea#

Sorting puts the extremes at known positions. You can then pair them, spend from one end and gain from the other, or place items in an order that never needs fixing.

Key points#

Pairing: if the heaviest item cannot pair with the lightest, it cannot pair with anyone.
Placing: process items in an order that later placements cannot disturb.
The proof question: "if you sort and pick this way, can anything else be better?"
Spot it: "pair up", "boats with at most two people", "exactly k taller people in front", n up to $10^5$ .

Sort key by problem#

Problem	Sort	Then
Boats to Save People	ascending	pair lightest with heaviest; heaviest always leaves
Queue Reconstruction	height desc, `k` asc	insert each person at index `k` ( $O(n^2)$ )
Array Partition	ascending	`sum(sorted(nums)[::2])`
Bag of Tokens	ascending	cheapest face up, priciest face down; track best score
Two City Scheduling	`cost_a - cost_b`	first half to A, rest to B
Hand of Straights	ascending	smallest card starts a group

Template#

sort items
i = 0, j = last index, count = 0
while i <= j:
    if items[i] and items[j] can share:
        i += 1                # the easy end joins the hard end
    j -= 1                    # the hard end always leaves now
    count += 1
return count

Pitfalls#

Sorting by height ascending in Queue Reconstruction. Later, taller insertions shift earlier counts.
Moving j only when a pair forms. The heaviest must leave every step.
Returning the final score in Bag of Tokens instead of the best score seen.
Picking a sort key by intuition alone. Check it on a small counterexample.

Say it in an interview#

"Sorting fixes where the extremes are, which makes the greedy provable."
"Tallest first, so a shorter person inserted later is invisible to everyone placed."