Medium · greedy
Minimum Waiting Time
Whoever goes first makes nobody wait; whoever goes last makes everybody wait. Every minute of a person's fill time is paid by everyone behind them — so the cheapest queue puts small times where they multiply least.
At a glanceSort ascending, then accumulate: person i waits the sum of everyone before them. <code>total += wait; wait += a[i]</code> after sorting is the whole solution.
Problem
Input: The first line is n (1 ≤ n ≤ 100). The second line has n integers (1 ≤ a ≤ 1000): each person's fill time in seconds.
Output: The minimum possible total waiting time, where a person's waiting time is everything before their own fill starts (their own fill does not count).
Samples:
| Input | Output |
|---|---|
4 | 8 |
1 | 0 |
For the sample, the best order is 1, 1, 3, 4: waits are 0, 1, 2, 5 — total 8. Any other order pays more; the sorted order is provably the minimum.
Your solution
Custom input for "Run my input"
Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.
Stuck? Hints
Hint 1 — Write what a swap changes
Take two neighbours x before y and imagine swapping them. Only those two waiting times change: with x first they pay y, with y first they pay x. Swapping is better exactly when y < x — so in an optimal queue every neighbour pair is ascending, which forces the whole queue to be sorted. That is the exchange argument, and it is how you prove a greedy instead of hoping.
Hint 2 — The sweep is a running prefix
After sorting, person i waits for the sum of a[0..i-1]. Instead of an inner loop, carry wait: for each person in order, total += wait; then wait += a[i];. Two additions per person, no second loop — the same prefix idea as Range Sum Queries.
Hint 3 — Waiting starts before, not after
The statement says a person's own fill time does not count as waiting. The running-prefix sweep gets this right for free — but if you instead compute prefix sums including a[i], every answer comes out too large by Σa[i], and the bug hides inside a plausible-looking number.
Solution (try it first!)
#include <iostream>
using namespace std;
int a[105];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
}
long long total = 0, wait = 0;
for (int i = 0; i < n; i++) {
total += wait;
wait += a[i];
}
cout << total << endl;
return 0;
}This is the shortest-job-first principle from operating systems, proved with four lines of exchange argument. Its sibling you already met: Minimum Coins was greedy with a different proof, and Bubble Sort is the machinery both reuse. When a greedy feels right, the exercise is always the same: find the swap that would improve any non-sorted answer.
Deep dive
Why this works
Exchange argument: take any queue that is not sorted ascending and swap an adjacent out-of-order pair (x before y with y < x). Only those two people's waits change, and they drop by x − y. So an unsorted queue can always be improved, and the unique local optimum is the sorted one — that is a proof, not a hope.
The cost
O(n²) for the bubble sort and O(n) for the sweep; with n ≤ 100 that is about 10,000 comparisons. Total wait fits easily in 64 bits (100 people × 1000 s ≈ 5 million seconds of waiting).
Where it goes wrong
- Counting each person's own fill time as waiting inflates every answer by Σa[i] — the sweep must add
waitBEFORE extending it with a[i]. - Sorting the display copy but sweeping the original array (or vice versa) — the answer silently corresponds to neither order.
- Forgetting that equal times can sit in any order among themselves: ties are free, do not complicate the sort for them.
Next step
The greedy sibling with a different proof is Minimum Coins — read the two exchange arguments side by side. The sort both reuse is Bubble Sort.
Two things to remember
- Fast first: every minute of the front person's time is paid by everyone behind.
- Swap argument = the proof template for greedy: find the swap that improves any unsorted answer.
🐞 This version fails — open it and try
Sweeps in arrival order — the queue was never sorted
#include <iostream>
using namespace std;
int a[105];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
long long total = 0, wait = 0;
for (int i = 0; i < n; i++) { // bug: no sorting first
total += wait;
wait += a[i];
}
cout << total << endl;
return 0;
}