Count Completed Jobs in a Serial Multi-Worker Pipeline

Problem Statement

You are building an orchestration engine for an automated data pipeline. The pipeline consists of K sequential stages indexed 0 to K - 1.

Each stage i is defined by a tuple (workers, duration):

• workers: The number of parallel workers available at stage i (workers >= 1).
• duration: The time required for one worker to process a single job at stage i (duration >= 0).

A sequence of job batches is submitted to the pipeline at time t = 0. You are given an array batches, where batches[j] represents the number of jobs in the j-th batch.

The pipeline operates under the following rules:

1. Worker Waves: Within stage i, a batch of B jobs is processed in parallel waves of up to workers jobs at a time. The number of waves required is ceil(B / workers). Each wave takes duration units of time. If B == 0, stage processing time is 0.
2. Stage Synchronization: Stage i + 1 cannot begin processing batch j until all jobs of batch j have completed stage i.
3. Single Batch per Stage: A stage can only process one batch at a time. Stage i cannot start processing batch j until it has completed batch j - 1.
4. Pipelining: Different stages can process different batches concurrently.
5. Completion Criterion: A batch is considered completed if and only if it finishes the final stage (K - 1) at or before deadline. If a batch does not finish by deadline, none of its jobs are counted.

Return the total number of jobs completed by deadline.

Function Signature

def count_completed_jobs(stages: list[tuple[int, int]], batches: list[int], deadline: int) -> int:
    pass

Examples

Example 1

stages = [(2, 3), (1, 4)]
batches = [3, 2]
deadline = 20

# Output: 3

Explanation:

• Batch 0 (3 jobs):
  • Stage 0 (workers = 2, duration = 3): ceil(3 / 2) = 2 waves = 2 * 3 = 6 time. Finishes at t = 6.
  • Stage 1 (workers = 1, duration = 4): Starts at t = 6. ceil(3 / 1) = 3 waves = 3 * 4 = 12 time. Finishes at t = 6 + 12 = 18.
  • Finishes at t = 18 <= 20. All 3 jobs complete.
• Batch 1 (2 jobs):
  • Stage 0: Starts at t = 6 (when Stage 0 frees up). ceil(2 / 2) = 1 wave = 1 * 3 = 3 time. Finishes at t = 9.
  • Stage 1: Starts at max(finish_stage_0 = 9, stage_1_free = 18) = 18. ceil(2 / 1) = 2 waves = 2 * 4 = 8 time. Finishes at t = 18 + 8 = 26.
  • Finishes at t = 26 > 20. Batch 1 does not complete before the deadline.
• Total completed jobs: 3.

Example 2

stages = [(3, 2)]
batches = [0, 5]
deadline = 4

# Output: 5

Explanation:

• Batch 0 has 0 jobs and takes 0 time, finishing at t = 0.
• Batch 1 (5 jobs) takes ceil(5 / 3) * 2 = 2 * 2 = 4 time at Stage 0, finishing at t = 4 <= 4.
• Total completed jobs: 0 + 5 = 5.

Constraints

• 1 <= len(stages) <= 1,000
• 1 <= stages[i][0] <= 10^6 (workers)
• 0 <= stages[i][1] <= 10^6 (duration)
• 0 <= len(batches) <= 10^4
• 0 <= batches[j] <= 10^9
• 0 <= deadline <= 10^18