Minimum Cache Processing Time
MediumBinary Search · Cisco
A cluster has n services numbered 1 to n. Request i has its data cached on service cache[i]. Every request must be processed by exactly one service, and you may choose which:
- If a request is processed by the service that caches it, it takes
1time unit. - If it is processed by any other service, it takes
2time units.
All services start at time 0 and run in parallel, but each service processes its assigned requests one after another, so a service finishes at the total time of the requests assigned to it.
Choose an assignment that minimizes the time at which the last service finishes, and return that minimum time. If there are no requests, return 0.
Example 1
- Input:
- n = 4, cache = [2, 2, 2, 2, 2, 2, 1]
- Output:
- 3
- Explanation
- Service 2 caches six requests. It keeps three (3 units) and hands one each to services 1, 3 and 4, which finish at 1 + 2 = 3, 2 and 2. Finishing by time 2 is impossible: service 2 would have to shed four requests, but the others only have room for two more.
Example 2
- Input:
- n = 2, cache = [1, 1, 1, 1]
- Output:
- 3
- Explanation
- Service 1 keeps three requests (3 units) and service 2 takes the fourth (2 units), so everything is done at 3. Splitting two and two is worse, because service 2 would need 2 + 2 = 4 units.
Example 3
- Input:
- n = 3, cache = [1, 2, 3]
- Output:
- 1
- Explanation
- Each service processes its own cached request in 1 unit, all at the same time.
Constraints
1 <= n <= 10^50 <= cache.length <= 10^51 <= cache[i] <= n