What if every customer rushes in at once?

The moment the neighborhood cafe 'CodeBean' opens, five customers pour in and order at the same time. The barista can make only one drink at a time, and each drink takes a different amount of time.

Cook times (min): [3, 1, 4, 1, 5]

Each customer waits until their own drink is ready. So whose drink should you make first to minimize the sum of everyone's waiting time?

The key: "an earlier order is added many times"

If one early order is slow, every customer waiting behind it waits that much longer too. So the cook time of the front order is added to the total not once, but many times.

More precisely: an order with cook time c placed at front position k is endured by its own customer plus everyone still behind, so c is added (N - k) times to the total.

The conclusion is natural: put the shortest order in the front slot that repeats the most. Clearing short drinks first keeps the cumulative wait of everyone behind as low as possible.

Why is "shortest first" always right? (exchange argument)

The intuition is nice, but is it *always* optimal? Look at just two adjacent orders: a in front and b right behind. Swapping only these two changes nothing for the other customers — only these two orders' own waits change.

•a first: a + (a + b)
•b first: b + (a + b)

The difference is exactly a - b. So if a > b, moving b to the front is always better. Since this holds for *every* adjacent pair, the state where no swap helps anymore is precisely ascending cook time — which is therefore optimal.

So the solution shrinks to this:

1. Sort cook times in ascending order

2. Accumulate from the front to get the running cook time (= each customer's finish time)

3. Sum the finish times — that's the minimum total waiting time

Sorting [3,1,4,1,5] gives [1,1,3,4,5], with finish times 1, 2, 5, 9, 14 — summing to 31 minutes. (Making them in the input order gives 38, which is worse.)

Seeing it makes "why it's minimal" stick

Hearing that it's "added (N - k) times" may not click. But once you lay the bars end-to-end on a time axis, it's a different story. The shorter the bar you put up front, the further left every following bar's start point shifts, and you can literally see the sum of finish times shrink.

•Draw each order as a cook-time bar
•Sort them shortest-first
•Watch the cumulative waiting time grow as each is processed

Following that as a step-by-step animation makes "*ah, that's* why shortest first" land instantly.

👉 Cafe Order Processing — watch the step-by-step visualization

This pattern (greedy = sort, then prefix sums) shows up in coding tests in countless disguises ("meeting room assignment", "job scheduling", "minimum average wait"). Learn the principle visually once, and no variant can shake you.