
Given a directed acyclic graph (DAG) with n pipeline stages labeled 0 to n-1, a list of directed edges edges where [u, v] means stage u must finish before v can start, and an array durations where durations[i] is the runtime of stage i, return a valid execution order and the bottleneck information. The bottleneck is defined as the critical path: the path with maximum total duration. Return the topological order, total pipeline runtime, one critical path, and the stages on that path.
Example 1:
Input: n = 5, edges = [[0,1],[0,2],[1,3],[2,3],[3,4]], durations = [3,2,4,5,1]
Output: {
"order": [0,1,2,3,4],
"total_time": 13,
"critical_path": [0,2,3,4],
"bottlenecks": [0,2,3,4]
}
Explanation: The longest dependency chain is 0 -> 2 -> 3 -> 4 with total duration 3 + 4 + 5 + 1 = 13.
Example 2:
Input: n = 4, edges = [[0,2],[1,2],[2,3]], durations = [5,1,2,7]
Output: {
"order": [0,1,2,3],
"total_time": 14,
"critical_path": [0,2,3],
"bottlenecks": [0,2,3]
}
Explanation: Stage 2 waits for both parents, and the slower incoming chain is 0 -> 2 -> 3.
1 <= n <= 10^50 <= len(edges) <= 2 * 10^5len(durations) == n1 <= durations[i] <= 10^9