Project Critical Path and Task Slack
LinkedIn projects often involve complex task dependencies and varying durations. Efficient project management requires identifying the minimum time to complete a project and understanding which tasks are critical (have no slack) and how much flexibility other tasks have. This problem asks you to analyze a project's task structure to determine its earliest possible completion time and calculate the "slack" for each individual task.
Implement a function calculateProjectMetrics that takes the total number of tasks, an array of their durations, and a list of dependencies between tasks.
The function should return two key metrics as an array/tuple:
result[i] represents the slack time for task i.numTasks: number: The total number of tasks, indexed from 0 to numTasks - 1.
durations: number[]: An array where durations[i] is the time required to complete task i.
dependencies: number[][]: A list of pairs [u, v], indicating that task u must be completed before task v can begin.
Return [projectCompletionTime: number, taskSlacks: number[]]: A tuple/array containing the minimum project completion time and an array of slack times for each task.
i is defined as LatestFinishTime[i] - EarliestFinishTime[i]. If a task is part of the critical path, its slack time will be 0.EarliestFinishTime[i] is the earliest time task i can finish. It is EarliestStartTime[i] + durations[i], where EarliestStartTime[i] is the maximum of EarliestFinishTime of all its direct predecessors (or 0 if no predecessors).LatestFinishTime[i] is the latest time task i can finish without delaying the overall project. It is LatestStartTime[i] + durations[i], where LatestStartTime[i] is the minimum of LatestStartTime of all its direct successors (or projectCompletionTime - durations[i] if no successors).Examples
Example 1
Input:
numTasks = 3, durations = [10, 5, 8], dependencies = [[0, 1], [1, 2]]
Output:
[23, [0, 0, 0]]
Note:
Tasks: 0 (10) -> 1 (5) -> 2 (8). Earliest Finish Times (EFT): EFT[0]=10, EFT[1]=15, EFT[2]=23. Project Completion Time = 23. Latest Finish Times (LFT): LFT[2]=23, LFT[1]=15, LFT[0]=10. Slacks: S[0]=10-10=0, S[1]=15-15=0, S[2]=23-23=0. All tasks are on the critical path.
Example 2
Input:
numTasks = 4, durations = [3, 2, 4, 5], dependencies = [[0, 2], [1, 2], [2, 3]]
Output:
[12, [0, 1, 0, 0]]
Note:
Tasks: 0 (3) -> 2 (4) -> 3 (5) 1 (2) -> 2 (4) EFT: EFT[0]=3, EFT[1]=2, EFT[2]=max(EFT[0],EFT[1])+4 = max(3,2)+4 = 7, EFT[3]=EFT[2]+5 = 7+5=12. Project Completion Time = 12. LFT: LFT[3]=12, LFT[2]=LFT[3]-5=7, LFT[0]=LFT[2]-4=3, LFT[1]=LFT[2]-4=3. Slacks: S[0]=3-3=0, S[1]=3-2=1, S[2]=7-7=0, S[3]=12-12=0. Task 1 has 1 unit of slack.
Example 3
Input:
numTasks = 5, durations = [2, 3, 4, 1, 5], dependencies = [[0, 2], [1, 3]]
Output:
[6, [0, 2, 0, 1, 1]]
Note:
Tasks: 0 (2) -> 2 (4) 1 (3) -> 3 (1) 4 (5) (independent) EFT: EFT[0]=2, EFT[1]=3, EFT[4]=5, EFT[2]=EFT[0]+4=6, EFT[3]=EFT[1]+1=4. Project Completion Time = max(2,3,6,4,5) = 6. LFT: LFT[2]=6, LFT[3]=5, LFT[4]=6. LFT[0]=LFT[2]-4=2, LFT[1]=LFT[3]-1=5. Slacks: S[0]=2-2=0, S[1]=5-3=2, S[2]=6-6=0, S[3]=5-4=1, S[4]=6-5=1.
Constraints
1 <= numTasks <= 10^51 <= durations[i] <= 10000 <= dependencies.length <= numTasks * (numTasks - 1) / 2 (maximum possible edges in a DAG)0 <= u, v < numTasksLoading editor...