Handmade Round Robin Wait
MediumQueues · Microsoft
A craftsperson serves clients in a queue, one hour of work at a time. Client i (in initial queue order) needs hours[i] hours of work in total.
Every hour, starting with hour 1:
- The client at the front of the queue receives one hour of work.
- If that was their last required hour, they leave; their finishing time is the number of the hour that just ended.
- Otherwise they go to the back of the queue.
Return the sum of all clients' finishing times, modulo 1_000_000_000 (i.e. the last nine digits of the sum, as an integer).
Note that hours[i] can be up to 10^9, so simulating hour by hour is far too slow.
Example 1
- Input:
- hours = [3, 1, 2]
- Output:
- 13
- Explanation
- Hour 1 goes to client 0, who moves to the back. Client 1 finishes at hour 2. Client 2 works in hour 3, client 0 in hour 4, then client 2 finishes at hour 5 and client 0 at hour 6. The sum is
2 + 5 + 6 = 13.
Example 2
- Input:
- hours = [2, 2]
- Output:
- 7
- Explanation
- The clients alternate: hours 1 and 2 give each of them one hour, then client 0 finishes at hour 3 and client 1 at hour 4, for a sum of 7.
Example 3
- Input:
- hours = [1000000000, 1000000000]
- Output:
- 999999999
- Explanation
- Client 0 finishes at hour
1999999999and client 1 at hour2000000000. The sum3999999999keeps its last nine digits,999999999.
Constraints
1 <= hours.length <= 10^51 <= hours[i] <= 10^9