Minimum Notification Time
MediumBinary Search · Netflix
A notification service has several worker processes running in parallel. Worker i needs exactly times[i] time units to deliver one notification, and it delivers notifications one after another with no gap, so by time t it has completed t // times[i] deliveries. Workers are independent and all start at time 0.
Given times and an integer total_devices, return the minimum integer time t at which the workers have, in total, completed at least total_devices deliveries.
Example 1
- Input:
- times = [2, 3, 7], total_devices = 6
- Output:
- 7
- Explanation
- At time 6 the workers have done
3 + 2 + 0 = 5deliveries, one short. At time 7 they have done3 + 2 + 1 = 6, so the answer is7.
Example 2
- Input:
- times = [4], total_devices = 3
- Output:
- 12
- Explanation
- A single worker finishes a delivery every 4 units, so the third one completes at time
12.
Example 3
- Input:
- times = [1, 100, 100], total_devices = 50
- Output:
- 50
- Explanation
- The worker with cost 1 finishes 50 deliveries by time 50 on its own, and the slow workers contribute nothing before time 100.
Constraints
- 1 ≤ times.length ≤ 105
- 1 ≤ times[i] ≤ 107
- 1 ≤ total_devices ≤ 107