Find the Minimum Processing Rate to Meet a Deadline
You have several independent workloads. During each hour, a worker chooses one workload and processes up to rate units from it. If that workload contains fewer than rate remaining units, the worker finishes it and the unused capacity in that hour cannot be applied to another workload. Find the smallest positive integer rate that finishes all workloads within hours hours.
Function Signature
def min_processing_rate(workloads: list[int], hours: int) -> int:
Inputs
-
workloads[i]
is the positive size of workload
i
.
-
hours
is the maximum total number of hourly processing slots.
-
It is guaranteed that
hours >= len(workloads)
, so a feasible rate exists.
Output
Return the minimum positive integer processing rate that completes every workload within the deadline.
Constraints
-
1 <= len(workloads) <= 100_000
-
1 <= workloads[i] <= 10^9
-
len(workloads) <= hours <= 10^9
-
The input array must not be mutated.
Examples
workloads = [3, 6, 7, 11]
hours = 8
output = 4
workloads = [30, 11, 23, 4, 20]
hours = 5
output = 30