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.
Implement:
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.int minimum makespan.A task can start only when all prerequisites are completed and a runner is available. Tasks cannot be preempted.
Example 1
n = 4, k = 2, durations = [3, 2, 4, 1], dependencies = [[0, 2], [1, 2], [2, 3]]8Example 2
n = 5, k = 3, durations = [5, 1, 1, 1, 1], dependencies = [[0, 1], [0, 2], [0, 3], [0, 4]]71 <= n <= 151 <= k <= n1 <= durations[i] <= 10^40 <= len(dependencies) <= n*(n-1)/2n = 4, k = 2, durations = [3, 2, 4, 1], dependencies = [[0, 2], [1, 2], [2, 3]]Output8WhyRun 0 and 1 first; 2 waits for both; then 3 waits for 2. Total time is 3+4+1 = 8 with the runner constraint.n = 5, k = 3, durations = [5, 1, 1, 1, 1], dependencies = [[0, 1], [0, 2], [0, 3], [0, 4]]Output7WhyTask 0 takes 5 and gates all others; the remaining four 1-second tasks finish in two waves on 3 runners.1 <= n <= 151 <= k <= n1 <= durations[i] <= 10^40 <= len(dependencies) <= n*(n-1)/2dependencies[i] = [a, b] with 0 <= a, b < n and a != bThe dependency graph is a DAGTasks are non-preemptive and runners are identicaldef min_deployment_time(n: int, k: int, durations: list[int], dependencies: list[list[int]]) -> int:
