Critical Path Slack

Problem

Compute the slack of every task in a weighted project DAG.

First compute earliest start times in topological order. Then compute the project duration and latest start times in reverse order without delaying the finish. Slack is latest minus earliest; nodes with zero slack form the critical path. edges is a list of [u, v, w] triples.

Hint

Slack is how long a task can wait without pushing the project end date.

Test cases

case 1

in: [4,[[0,1,3],[1,3,2],[0,2,2],[2,3,4]]]

expected: [0,1,0,0]

case 2

in: [3,[[0,1,5],[1,2,3]]]

expected: [0,0,0]

case 3

in: [3,[[0,1,1],[0,2,10]]]

expected: [0,9,0]

Starter codePython

import heapq
def critical_path_slack(n, edges):
    # Your code here
    pass

3 test cases · run your code against them in the editor