Problem

At Stripe, a CI pipeline consists of n non-preemptive tasks with durations and prerequisite dependencies (a DAG). You have k identical runners that can execute tasks in parallel. Compute the minimum total time (makespan) to finish all tasks.

Specification

Implement:

• Input: n: int, k: int, durations: list[int], dependencies: list[list[int]] where each dependency [a, b] means task a must finish before task b can start.
• Output: int minimum makespan.

A task can start only when all prerequisites are completed and a runner is available. Tasks cannot be preempted.

Examples

Example 1

• Input: n = 4, k = 2, durations = [3, 2, 4, 1], dependencies = [[0, 2], [1, 2], [2, 3]]
• Output: 8
• Explanation: Run 0 and 1 first; 2 waits for both; then 3 waits for 2.

Example 2

• Input: n = 5, k = 3, durations = [5, 1, 1, 1, 1], dependencies = [[0, 1], [0, 2], [0, 3], [0, 4]]
• Output: 7
• Explanation: Task 0 gates all others; the four 1s finish in two waves on 3 runners.

Constraints

• 1 <= n <= 15
• 1 <= k <= n
• 1 <= durations[i] <= 10^4
• 0 <= len(dependencies) <= n*(n-1)/2
• Dependency graph is a DAG