Least Total Waiting Time
service lists how many minutes each customer at a counter needs. The counter serves one customer at a time with no breaks, and you choose the order. A customer's waiting time is the number of minutes that pass before their own service starts, so whoever goes first waits 0.
Return the smallest possible total waiting time, summed over all customers. The smallest total is the same for every order that achieves it, so no tie rule is needed. Return 0 if service is empty or has a single customer.
Example 1
Serve the 1-minute customer first, then the 2-minute one, then the 3-minute one: they wait 0, 1 and 3 minutes, 4 in total.
Example 2
Two customers of 10 and 1: the 1-minute customer goes first and the other waits 1 minute.
Constraints
0 <= len(service) <= 1001 <= service[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Most Tasks in a Time BudgetBeginner
- Only the Best CountBeginner
- Shortest Walk to SeatsBeginner
- Stepping StonesBeginner
- Third One FreeBeginner
- Two Numbers From Four DigitsBeginner
- Array PartitionEasy
- Assign CookiesEasy