Critical Path Length of a Pipeline DAG

mediumPROPipelines, Reliability & CostSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

Compute the minimum total time to run a CI pipeline where independent stages run in parallel — the critical path (longest-duration path) through the dependency DAG.

Background

Each stage has a duration and depends on prior stages. A stage cannot start until all its dependencies finish. The earliest finish time of a stage is duration + max(earliest finish of its deps) (or just its duration if it has none). The pipeline's makespan is the maximum finish time over all stages.

Your Task

def critical_path(stages):

stages: dict mapping name -> {"duration": number, "deps": [names]}.
Return the makespan (number). Assume the DAG is acyclic.

Input Format

stages (dict).

Output Format

A number (total time).

Sample

print(critical_path({"a": {"duration": 3, "deps": []}, "b": {"duration": 4, "deps": ["a"]}}))

Output:

Example

Input

print(critical_path({"a": {"duration": 3, "deps": []}, "b": {"duration": 4, "deps": ["a"]}}))

Output

Reasoning

Identify the dependency chain: Stage "b" depends on stage "a", so "a" must finish before "b" can start.
Calculate the earliest finish time for stage "a": Since it has no dependencies, its finish time is simply its duration, $3$ .
Calculate the earliest finish time for stage "b": It waits for its dependency "a" to finish, so its start time is $3$ ; adding its own duration gives $3 + 4 = 7$ .
Determine the pipeline makespan: This is the maximum finish time across all stages, which is $\max(3, 7) = 7$ .
The final output is 7

Constraints

finish(stage) = duration + max(finish(dep)) (0 if no deps).
Makespan = max finish over all stages.
DAG is acyclic; use memoization.

Learn this in

ML InfrastructureSystems & Networking Why GPUs? The Parallel Computing MindsetGPU Basics with Triton

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 Pipeline Stages Ready to Runeasy

Concept primerPREVIEW

1. Background Knowledge

This problem models a Directed Acyclic Graph (DAG) where nodes represent pipeline stages and edges represent dependencies. In a CI/CD context, a stage cannot begin until every stage it depends on has completed. The goal is to find the critical path, which is the longest path through the graph in terms of total duration. This path determines the makespan, or the minimum total time required to complete the entire pipeline, because all other paths will finish earlier or simultaneously.

The key insight is that the earliest finish time of a node is not simply the sum of its dependencies' times, but rather its own duration plus the maximum earliest finish time among all its dependencies. If a stage has no dependencies, its earliest finish time is just its own duration. This is a classic example of dynamic programming on a DAG, where the optimal substructure allows us to compute the answer for each node based on the answers of its predecessors.

Because the graph is guaranteed to be acyclic, we can process nodes in a specific order (topological order) to ensure that when we compute a node's value, all its dependencies have already been computed. This avoids the need for cycle detection or recursion depth management that would be required for general graphs.

2. Algorithm Approach

The standard approach is Topological Sort combined with Dynamic Programming.

Topological Sort: Determine an ordering of the nodes such that for every directed edge $u \to v$ , node $u$ comes before node $v$ in the ordering. This can be done using Kahn's algorithm (BFS-based) or DFS-based post-order traversal.
DP Traversal: Iterate through the nodes in topological order. For each node, calculate its earliest finish time using the formula:

\text{finish}[v] = \text{duration}[v] + \max(\text{finish}[u] \text{ for all } u \in \text{deps}(v))

If a node has no dependencies, the max term is $0$ . 3. Result Extraction: The makespan is the maximum value in the finish array across all nodes.

This approach ensures that when we process a node, all its dependencies have already been processed, so their finish times are known.

3. Step-by-Step Strategy

Build the Graph:

Create an adjacency list or simply use the input dictionary directly.
Calculate the in-degree for each node (number of dependencies).
Identify all nodes with in-degree $0$ (no dependencies).

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results