Calculate Ordered Job Makespan Across Parallel Workers

Problem Statement

You are building a job execution engine for a data integration pipeline. You are given an array of non-negative integers durations, where durations[i] represents the execution time in seconds of the i-th job in arrival order, and an integer k representing the number of identical parallel workers.

Workers are indexed from 0 to k - 1 and are all available at time t = 0.

Jobs must be dispatched strictly in queue order:

• Job 0 is dispatched first, followed by job 1, and so on.
• Each job is assigned to the worker that becomes free earliest.
• If multiple workers are free at the same time, the job is assigned to the worker with the lowest index.
• Once a worker starts a job, it runs continuously for durations[i] seconds without interruption.

Return the makespan of the pipeline—the total elapsed time from t = 0 until all jobs have finished execution.

Function Signature

def calculate_makespan(durations: list[int], k: int) -> int:
    pass

Constraints

• 0 <= len(durations) <= 10^5
• 1 <= k <= 10^5
• 0 <= durations[i] <= 10^9
• Results can exceed standard 32-bit signed integer limits; 64-bit integer support is required.

Examples

Example 1

Input: durations = [3, 2, 4, 1, 5], k = 2
Output: 9

Explanation:

• t = 0: Worker 0 takes job 0 (duration 3, finishes at t = 3). Worker 1 takes job 1 (duration 2, finishes at t = 2).
• t = 2: Worker 1 becomes free and takes job 2 (duration 4, finishes at t = 6).
• t = 3: Worker 0 becomes free and takes job 3 (duration 1, finishes at t = 4).
• t = 4: Worker 0 becomes free and takes job 4 (duration 5, finishes at t = 9).
• All jobs finish by t = 9. The makespan is 9.

Example 2

Input: durations = [10, 20, 15], k = 5
Output: 20

Explanation: There are more workers than jobs. Workers 0, 1, and 2 each take one job at t = 0. The longest running job takes 20 seconds, so the makespan is 20.

Example 3

Input: durations = [], k = 4
Output: 0

Explanation: With no jobs to process, the total elapsed time is 0.

Edge Cases to Consider

• durations is empty: should immediately return 0.
• k >= len(durations): every job can start at t = 0; the makespan is simply max(durations) (or 0 if empty).
• Jobs with duration 0: they complete instantaneously and free the worker at the same timestamp.