CI Pipeline Critical Path

hardFREEPipelines, Reliability & CostSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

A CI pipeline's wall-clock time is not the sum of its jobs — jobs with no dependency between them run in parallel on separate runners. It is the length of the longest dependency chain. Compute that, and identify the jobs on it, because shaving a minute off any other job changes nothing.

Background

Model the workflow as a DAG: each job has a duration and a needs list. Assume unlimited runners, so a job starts the instant all of its dependencies have finished.

Forward pass — earliest finish:

EF(j) = duration(j) + max(EF(d) for d in needs(j))     # 0 if no dependencies
total = max(EF(j) over all j)

Backward pass — latest finish without delaying the pipeline:

LF(j) = total                                  if nothing depends on j
LF(j) = min(LF(c) - duration(c) for c in dependents(j))   otherwise

A job's slack is LF(j) - EF(j). Jobs with zero slack are critical: delay one by a minute and the whole pipeline slips by a minute. Everything else has room to spare. Note there can be several parallel critical chains at once — every zero-slack job belongs in the answer, not just one path.

Your Task

Implement:

def critical_path(jobs):

Return a dict with keys "total_minutes" (int) and "critical_jobs" (the names with zero slack, sorted alphabetically), in that order.

Input Format

jobs: list of dicts with "name" (unique string), "duration" (positive int, minutes) and "needs" (list of job names, possibly empty). The graph is a DAG and every name in needs exists.

Output Format

{"total_minutes": int, "critical_jobs": [sorted names]}

Sample

jobs = [{"name": "checkout", "duration": 1, "needs": []},
        {"name": "lint", "duration": 2, "needs": ["checkout"]},
        {"name": "unit-tests", "duration": 8, "needs": ["checkout"]},
        {"name": "build-image", "duration": 6, "needs": ["lint", "unit-tests"]},
        {"name": "deploy", "duration": 3, "needs": ["build-image"]}]
print(critical_path(jobs))

Output:

{'total_minutes': 18, 'critical_jobs': ['build-image', 'checkout', 'deploy', 'unit-tests']}

lint runs in parallel with the 8-minute test job and finishes long before build-image needs it, so it has slack and is not on the critical path — making lint faster would not save a second.

Example

Input

jobs = [{"name": "checkout", "duration": 1, "needs": []}, {"name": "lint", "duration": 2, "needs": ["checkout"]}, {"name": "unit-tests", "duration": 8, "needs": ["checkout"]}, {"name": "build-image", "duration": 6, "needs": ["lint", "unit-tests"]}, {"name": "deploy", "duration": 3, "needs": ["build-image"]}]
print(critical_path(jobs))

Output

{'total_minutes': 18, 'critical_jobs': ['build-image', 'checkout', 'deploy', 'unit-tests']}

Reasoning

Forward pass: checkout finishes at 1, lint at 3, unit-tests at 9, build-image waits for the later of the two (9) and finishes at 15, deploy at 18. Backward pass: deploy, build-image, unit-tests and checkout all have latest finish equal to their earliest finish, so slack 0. lint could finish as late as 9 but finishes at 3, so it carries 6 minutes of slack and is not critical.

Constraints

1 <= len(jobs) <= 200; names are unique and every entry in needs refers to an existing job
Durations are positive ints (minutes); the graph is guaranteed acyclic
Runners are unlimited — a job starts as soon as all its dependencies finish
A job is critical when latest_finish - earliest_finish == 0
critical_jobs is sorted alphabetically and may contain several parallel chains

Learn this in

CI/CD & PipelinesSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primer

1. Background Knowledge

This problem models a Directed Acyclic Graph (DAG) where nodes represent jobs and edges represent dependencies. The core concept is Critical Path Method (CPM), a project management technique used to determine the minimum time required to complete a project. In a CI/CD pipeline with unlimited parallel runners, the total execution time is dictated by the longest chain of dependent tasks, known as the critical path. Any delay in a critical job directly delays the entire pipeline, whereas non-critical jobs have slack (or float), meaning they can be delayed without affecting the final deadline.

To solve this, we utilize two fundamental passes over the DAG:

Forward Pass: Computes the Earliest Finish (EF) time for each job. This determines when a job can finish if all its predecessors finish as early as possible. The maximum EF across all jobs is the total pipeline duration.
Backward Pass: Computes the Latest Finish (LF) time for each job. This determines the latest a job can finish without delaying the overall pipeline completion time.

The slack of a job is defined as $LF(j) - EF(j)$ . Jobs with zero slack are critical. Identifying these jobs allows engineers to prioritize optimization efforts effectively, as reducing the duration of non-critical jobs yields no benefit to the total wall-clock time.

2. Algorithm Approach

The standard approach for CPM involves Topological Sorting combined with dynamic programming-like updates. Since the graph is a DAG, we can process nodes in an order that respects dependencies.

Graph Construction: Convert the input list of jobs into an adjacency list representation. We need two views:

adj: Maps a job to its dependents (children) for the backward pass.
in_degree: Tracks the number of dependencies for each job to facilitate topological sorting.

Topological Sort (Kahn's Algorithm): Use a queue to process jobs with zero in-degree. This ensures we process jobs only after all their dependencies are resolved. This ordering is crucial for the forward pass.
Forward Pass: Iterate through the topological order. For each job, calculate its EF based on the maximum EF of its dependencies plus its own duration.
Backward Pass: Iterate through the reverse topological order. For each job, calculate its LF based on the minimum LF of its dependents minus their durations. Jobs with no dependents have an LF equal to the total pipeline time.
Slack Calculation: Compute slack for each job and filter those with zero slack.

3. Step-by-Step Strategy

Parse Input: Create a dictionary mapping job names to their properties (duration, needs). Also, build an adjacency list dependents where dependents[u] contains all jobs that need u.
Compute In-Degrees: Calculate the number of dependencies for each job. Initialize a queue with all jobs having zero in-degree.
Topological Sort & Forward Pass:

Initialize EF dictionary with 0 for all jobs.
While the queue is not empty, pop a job u.
For each dependent v of u:
Update EF[v] = max(EF[v], EF[u] + duration[u]).
Decrement in_degree[v]. If it becomes 0, push v to the queue.
Store the topological order in a list topo_order.

Determine Total Time: The total_minutes is the maximum value in the EF dictionary.
Backward Pass:

Initialize LF dictionary. Set LF[j] = total_minutes for all jobs j that have no dependents (sinks). For others, initialize with infinity.
Iterate through topo_order in reverse.
For each job u, if it has dependents, update its LF: $LF(u) = \min_{v \in \text{dependents}(u)} (LF(v) - \text{duration}(v))$ Note: If a job has no dependents, its LF remains total_minutes.

Identify Critical Jobs:

For each job, calculate slack = LF[j] - EF[j].
Collect all job names where slack == 0.

Format Output: Sort the critical job names alphabetically and return the dictionary with total_minutes and critical_jobs.

4. Common Pitfalls

Incorrect Backward Pass Initialization: Ensure that jobs with no dependents (leaf nodes in the dependency graph) are correctly initialized with LF = total_minutes. If you initialize all LF to infinity and only update via dependents, leaf nodes will remain infinity, leading to incorrect slack calculations.
Reverse Topological Order: The backward pass must process nodes in reverse topological order. Processing in forward order would mean you try to calculate LF before the LF of dependents is known.
Multiple Critical Paths: The problem states that all zero-slack jobs must be returned. Do not stop after finding one path. There may be parallel critical chains.
Graph Cycles: Although the problem guarantees a DAG, always ensure your topological sort detects cycles in general cases. If the queue empties before all nodes are processed, a cycle exists.
Indexing vs. Names: Be careful when mapping between job names and indices. Using a dictionary keyed by job name is often safer and cleaner than converting names to integer indices.

5. Time & Space Complexity

Time Complexity: $O(V + E)$ , where $V$ is the number of jobs and $E$ is the number of dependency edges.
Building the graph and in-degrees takes $O(V + E)$ .
Topological sort (Kahn's algorithm) visits each node and edge once: $O(V + E)$ .
Forward and backward passes each iterate through all nodes and edges once: $O(V + E)$ .
Sorting the critical jobs takes $O(K \log K)$ , where $K$ is the number of critical jobs ( $K \le V$ ). This is dominated by $O(V + E)$ .
Space Complexity: $O(V + E)$ .
We store the adjacency list (dependents), in_degree array, EF and LF dictionaries, and the topological order list. All scale linearly with the size of the graph.

solution.py

Python 3.13

Test results