Compute Earliest Completion Times
NetflixSoftware Engineer · OnsiteLast updated
This question evaluates understanding of directed acyclic graphs, dependency resolution, computation of earliest task completion times, and cycle detection within prerequisite relationships.
You are given n tasks numbered from 0 to n - 1. Each task i has a positive duration duration[i].
You are also given a list of prerequisite relationships prerequisites, where [a, b] means task a must be fully completed before task b can start.
Assume there are unlimited workers, so any number of tasks may run in parallel as long as their prerequisites are satisfied.
Implement a function that returns:
- the earliest completion time for every task, and
- the minimum total time required to complete all tasks.
If the prerequisite graph contains a cycle, return an error or a special value indicating that the schedule is impossible.
Example:
n = 4
duration = [3, 2, 4, 1]
prerequisites = [[0, 2], [1, 2], [2, 3]]
Task 0 finishes at time 3.
Task 1 finishes at time 2.
Task 2 can start after both 0 and 1 finish, so it starts at time 3 and finishes at time 7.
Task 3 starts at time 7 and finishes at time 8.
Return earliestFinish = [3, 2, 7, 8], totalTime = 8.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.