Frontend School

Project Critical Path and Task Slack

DSA
hard

Project Critical Path and Task Slack

Hard
Graph
Topological Sort
Dynamic Programming
Critical Path

Overview

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.

What you need to do / 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:

  1. The minimum total time required to complete the entire project (also known as the critical path duration).
  2. An array where result[i] represents the slack time for task i.

Input & output

  • 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.

Clarifications

  • The project graph is guaranteed to be a Directed Acyclic Graph (DAG). There will be no cycles.
  • Tasks can be performed in parallel as long as their dependencies are met.
  • A task with no predecessors can start at time 0.
  • Slack time for a 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

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= numTasks <= 10^5
  • 1 <= durations[i] <= 1000
  • 0 <= dependencies.length <= numTasks * (numTasks - 1) / 2 (maximum possible edges in a DAG)
  • 0 <= u, v < numTasks
  • The graph formed by tasks and dependencies is always a Directed Acyclic Graph (DAG).

Out of scope

  • Handling invalid inputs (e.g., negative durations, out-of-bounds task indices).
  • Detecting or handling cycles in the dependency graph.
  • Optimizing for resource constraints (e.g., limited workers).

What interviewers evaluate

  • Correct application of topological sort for both forward (earliest time) and backward (latest time) calculations.
  • Efficiency of the algorithm in terms of time and space complexity (should be linear with respect to tasks and dependencies).
  • Clear, well-structured, and readable code, demonstrating good problem-solving practices.
  • Ability to derive and explain the concepts of critical path and task slack.

Loading editor...