Shortest job first
Serve customers in the order that makes the total waiting time smallest, and see why swapping two neighbours proves the order is best. About 15 minutes.
Who waits for whom
A single counter serves customers one at a time. Each customer needs some minutes. A customer waits for everyone served before them, not for their own service.
So the first job in the line is waited on by every later customer, the second by all but one, and so on. A long job early is paid for many times. A short job early is paid for cheaply.
The exchange argument
Why is shortest first really best? Take any order where a long job L is served right before a short job S. Swap them.
Everyone else waits the same, since the pair still takes L plus S together. The job S now waits less, because it no longer waits for L, while L waits only a little more. The total never rises. Repeat swaps until no long job sits before a short one: that is the sorted order.
order = sorted(times)
running = 0
for t in order:
running += tThe first customer waits 0. Total wait 0.
Jobs take 4 and 1 minutes. Which order gives the smaller total wait?
- A1 first, then 4 (total wait 1)
- B4 first, then 1 (total wait 4)
- CBoth orders give the same total
Show the answer
1 first, then 4 (total wait 1). The second job waits 1 minute, and the first waits 0.
Least total waiting time
Customers arrive at a counter together, and you are given the minutes each one needs in an array times. The counter serves one customer at a time. A customer's waiting time is the minutes they wait before their own service starts. Return the smallest possible total waiting time of all customers.
times = [3, 2, 5] → 7
0 ≤ times.length ≤ 100,000 · 1 ≤ times[i] ≤ 1,000