Calculate Ordered Job Makespan Across Parallel Workers
A single stage has jobs with different durations and a fixed number of identical workers. Jobs must be assigned in the order they appear. At time 0, assign jobs in order to available workers. Whenever a worker finishes, immediately assign that worker the next unassigned job. A job cannot be split or processed by more than one worker. Return the time when all jobs are complete.
Function Signature
def calculate_stage_duration(job_durations: list[int], num_workers: int) -> int:
Inputs
-
job_durations[i]
is the positive integer duration of job
i
.
-
num_workers
is the number of identical workers available at time 0.
-
If several workers become free at the same time, any of those tied workers may receive the next job; this does not change the makespan.
Output
Return the makespan, the earliest time at which all jobs have completed. Return 0 when there are no jobs.
Constraints
-
0 <= len(job_durations) <= 200_000
-
1 <= job_durations[i] <= 10^9
-
1 <= num_workers <= 200_000
-
The result fits in a signed 64-bit integer.
-
The input array must not be mutated.
Examples
job_durations = [5, 2, 10, 4, 8]
num_workers = 2
output = 17
job_durations = [4, 7]
num_workers = 5
output = 7
job_durations = []
num_workers = 3
output = 0