CI Pipeline Critical Path

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.