1050. Seating Everyone With the Fewest Steps

n seats stand at given positions on a line, and n students stand at given positions on the same line. Every student must end up on a seat, one student per seat. Moving a student one unit costs one step.

Print the fewest total steps.

seats 3 1 5, students 2 7 4 -> 4 seats 4 1 5 9, students 1 3 2 6 -> 7 seats 1 2, students 2 1 -> 0 each student walks to the other seat

Positions may repeat on either side, and a student already standing on a seat still has to be ASSIGNED to one, which may not be the one under their feet.

## What most people try first

Try every assignment. That is n! and the input allows n = 100000. Even n = 12 is 479001600 assignments.

The other instinct, "send each student to their nearest seat", is wrong because two students may share a nearest seat while a third seat goes empty. On seats 1 2 and students 2 2 the nearest-seat rule sends both to seat 2.

## Sort both lists and pair them in order

sort the seats sort the students answer = sum over i of |seat[i] - student[i]|

## Why sorted order is optimal

Take any assignment and look for a CROSSING: two students x < y sent to seats p and q with p > q, so the lower student goes to the higher seat. Show that uncrossing them never costs more, and the sorted pairing is the only assignment with no crossings.

Uncrossing means sending x to q and y to p. Compare

crossed: |x - p| + |y - q| uncrossed: |x - q| + |y - p|

with x <= y and q < p. Write it as: both sides are the total length of two segments covering the same four points. The uncrossed pairing is [x,q] with [y,p] and the crossed one is [x,p] with [y,q], and the crossed pair of segments contains the uncrossed pair piece by piece, because the crossed pairing spans from the smallest point to the largest. So

|x - q| + |y - p| <= |x - p| + |y - q|

for every arrangement of the four values. Checking the handful of orderings of x, y, q, p by hand is worth doing once; the inequality is tight when the two segments do not overlap.

Every crossing can therefore be removed without increasing the total, and removing crossings strictly reduces the number of inversions, so the process ends. It ends at the sorted pairing.

## The trap

Sorting only ONE of the two lists. That passes any test where the other list happens to arrive sorted, and the samples here deliberately give both lists out of order.

## Overflow

n reaches 100000 and positions reach 10^9, so the total reaches 10^14. A single distance fits in 32 bits, whose limit is 2147483647, but the sum does not, and the short test with three students a billion from their seats totals 3 * 10^9 on its own.

## Where this sits

Problem #611 walks two sorted lists too, but there the pairing is a FEASIBILITY question, whether a biscuit satisfies a child, and the answer is a count. Here every pairing is legal and the question is which one is cheapest, which is why the argument is about crossings rather than about who is served.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ seat[i] ≤ 1000000000` - `0 ≤ student[i] ≤ 1000000000`