1102. Finish the Short Jobs First

One counter serves n customers. Customer i takes t[i] minutes. Everybody must be served, one at a time, in whatever order you choose, and the counter never idles.

A customer's WAITING time is the number of minutes that pass before their service starts. Print the smallest possible total waiting time over all customers.

times 5 1 4 2 -> 11 serve 1, 2, 4, 5: waits 0, 1, 3, 7 times 1 2 3 4 5 -> 20 waits 0, 1, 3, 6, 10 times 7 7 7 -> 21 waits 0, 7, 14

The first line is worth doing by hand. Serving in the order 1, 2, 4, 5 the waits are 0, then 1, then 1 + 2 = 3, then 1 + 2 + 4 = 7, adding to 11. Serving in the given order 5, 4, 1, 2 the waits are 0, 5, 9, 10, adding to 24, more than twice as much.

## What most people try first

Trying every order. There are n! of them, and at n = 12 that is already 479001600; at n = 100000 the number has more digits than there are atoms worth counting.

The second thing people try is serving the LONGEST customer first, on the theory that the big job should be got out of the way. That is exactly backwards, and the example above shows why: the long job's own waiting time is 0 either way, but everybody behind it waits through the whole of it.

## The method

Sort ascending and serve in that order, accumulating as you go.

sort t ascending total = 0 elapsed = 0 for x in t: total = total + elapsed elapsed = elapsed + x

One sort and one pass, O(n log n).

Equivalently, the customer at sorted position i counting from 0 is waited on by the n - 1 - i customers behind them, so the answer is the sum of t[i] * (n - 1 - i). Both forms give the same number and the running one is easier to get right.

## Why ascending is optimal

Take any order that is not ascending. Somewhere in it two ADJACENT customers are out of order: customer a is served immediately before customer b, and t[a] > t[b].

Swap them. Nobody before the pair is affected, because the time at which the pair begins is unchanged. Nobody after the pair is affected either, because the pair still takes t[a] + t[b] minutes in total, so everything behind them starts at exactly the same moment.

Only the two of them change. Before the swap their waits are W and W + t[a]. After the swap they are W and W + t[b]. Since t[b] < t[a], the total falls by t[a] - t[b], which is strictly positive.

So every non-ascending order can be strictly improved, which means no non-ascending order is optimal, and the ascending one is. That is the adjacent-swap form of the exchange argument, and it is the cleanest one there is: the swap is local, everything outside the pair is untouched, and the comparison that falls out, t[a] > t[b], IS the sort key.

## The boundary that breaks a careless implementation

The last customer's own service time never enters the answer, because nobody waits behind them. A loop that adds elapsed after updating it rather than before counts every service time once too often and reports a number that is larger by the total of all times.

Times of 0 are allowed and change nothing, which is a useful check that the loop is not special-casing anything.

## Sizes

n reaches 10^5 and each time reaches 10^9. The worst total waiting time is when every customer takes the maximum, giving 10^9 * n * (n - 1) / 2, which is about 5 * 10^18. That fits in a signed 64-bit integer, whose limit is about 9.2 * 10^18, and is enormously past the 2147483647 limit of a 32-bit one. Even five customers of 10^9 minutes give 10^10, so the accumulator must be 64 bits from the start.

## A related problem

Problem #1108 is this question with k counters running in parallel, where the answer stops being a running sum and becomes a weight per sorted position. Problem #1110 keeps one counter but gives each customer an IMPORTANCE, and then ascending by time is wrong and ascending by time divided by importance is right.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ t[i] ≤ 1000000000` - the answer can reach about `5 * 10^18`, so it needs 64 bits