655. Sending Half To Each City
2n people are to be flown to interviews, exactly n to city A and n to city B. For each
person the two fares are given.
Print the smallest possible total fare.
fares (10,20) (30,200) (400,50) (30,20) -> 110
fares (1,2) (2,1) -> 2
## Why the cheapest-first greedy fails
Sending each person to their own cheaper city ignores the requirement that exactly half go to each. Repairing it afterwards by moving whoever is cheapest to move is closer, and still not obviously right.
The clean way is to change what is being minimised.
## Send everyone to B, then buy back the cheapest upgrades
Suppose everyone flies to B. That costs sum of b. Now n people must be switched to A, and
switching person i changes the total by
a[i] - b[i]
which may be negative, meaning a saving. To minimise the total, choose the n people with the
SMALLEST value of a[i] - b[i].
So: sort by a - b, send the first half to A and the second half to B.
## Why that is optimal
The total is sum of b plus the sum of the chosen differences, and sum of b is fixed. So the
problem is exactly "choose n items with the smallest values", and sorting answers it. There
is no interaction between the choices, which is precisely why a greedy works here and does not
in problems where the choices constrain each other.
Recasting a constrained choice as "a fixed cost plus a free choice of n differences" is the
move worth taking away.
## Where the two pointers are
After sorting, the answer reads the first half from one end and the second half from the other, which is a single pass with a cursor at each end of the sorted list. The sort is doing the real work, and the pointers are how the result is collected.
## Boundaries
Two people is the smallest input and the answer is whichever assignment is cheaper. Identical fares for everyone give the same total whatever the split.
## Overflow
200000 people with fares up to 1000 give a total up to 2 * 10^8, which fits in 32 bits,
but the intermediate sum of b plus negative differences is safer in 64.
## Cost
Time O(n log n) for the sort. Space O(n).
Constraints - `2 ≤ m ≤ 200000` and `m` is even - `1 ≤ each fare ≤ 1000`
Input
The first line contains an even integer m, the number of people.
Each of the next m lines contains two integers, the fare to city A and the fare to city B.
Output
Print one integer, the smallest total fare.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.