Calculate Ordered Job Makespan Across Parallel Workers
Company: Plaid
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# 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
```python
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
```text
job_durations = [5, 2, 10, 4, 8]
num_workers = 2
output = 17
```
```text
job_durations = [4, 7]
num_workers = 5
output = 7
```
```text
job_durations = []
num_workers = 3
output = 0
```
Quick Answer: Find the makespan when ordered jobs with different durations are dispatched to a fixed pool of identical workers. The exercise tests event-driven scheduling, tie handling, choosing an efficient representation of worker availability, empty workloads, excess workers, and 64-bit runtime bounds.
A single pipeline stage has a list of jobs and a fixed number of identical
workers. `job_durations[i]` is the duration of job `i`, and all `num_workers`
workers are idle at time 0.
Jobs are handed out strictly in the order they appear in `job_durations`:
- At time 0, jobs are assigned in order to the idle workers, one job per
worker, until either the workers or the jobs run out.
- Whenever a worker finishes its current job, it immediately takes the next
job that has not been assigned yet.
- A job runs on exactly one worker. It cannot be split, paused, reordered, or
moved to another worker.
Return the **makespan**: the earliest time at which every job has finished.
Return `0` when `job_durations` is empty.
If several workers become free at the same instant, any one of them may take
the next job. That choice never changes the makespan, so the answer for a
given input is unique.
`job_durations` must not be mutated.
## Output
A single integer: the makespan.
## Example 1
```text
job_durations = [5, 2, 10, 4, 8]
num_workers = 2
output = 17
```
Timeline: at T=0 worker A starts job `5` and worker B starts job `2`. At T=2
worker B is free and takes job `10` (finishing at T=12). At T=5 worker A is
free and takes job `4` (finishing at T=9). At T=9 worker A takes job `8` and
finishes at T=17. The last job finishes at T=17, so the makespan is 17.
Note that reordering the jobs is not allowed: sorting them ascending or
descending produces a different, wrong answer here.
## Example 2
```text
job_durations = [4, 7]
num_workers = 5
output = 7
```
There are more workers than jobs, so both jobs start at T=0 and the makespan
is simply the longest duration, 7. The three unused workers never receive a
job.
## Example 3
```text
job_durations = []
num_workers = 3
output = 0
```
Constraints
- 0 <= len(job_durations) <= 200_000
- 1 <= job_durations[i] <= 10^9
- 1 <= num_workers <= 200_000
- num_workers is independent of len(job_durations) and may exceed it
- The result fits in a signed 64-bit integer
- The makespan can reach 200_000 * 10^9 = 2 * 10^14, which overflows a signed 32-bit int: accumulate in long (Java) / long long (C++)
- The input array must not be mutated
Examples
Input: ([5, 2, 10, 4, 8], 2)
Expected Output: 17
Input: ([4, 7], 5)
Expected Output: 7
Hints
- The job order is fixed, so the only thing you ever need to look up is which worker becomes free earliest. Which data structure answers that in O(log k)?
- Workers beyond min(num_workers, len(job_durations)) never receive a job, so you never need to track more than that many free-times even when num_workers is 200,000.
- The answer is the largest completion time across all workers, not the finish time of the worker that happened to receive the last job in the array.