Katkat

Compute Earliest Completion Times

NetflixSoftware Engineer · Onsite

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