Compute Earliest Completion Times
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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:
```text
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.
```
Quick Answer: 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 prerequisite relationships `prerequisites`, where `[a, b]` means task `a` must be fully completed before task `b` can start.
There are unlimited workers, so any number of tasks may run in parallel as long as their prerequisites are satisfied.
Return a tuple `(earliest_finish, total_time)` where:
- `earliest_finish[i]` is the earliest time task `i` can be completed, and
- `total_time` is the minimum time required to finish all tasks.
If the prerequisite graph contains a cycle, return `None` to indicate that the schedule is impossible.
Constraints
- `0 <= n <= 200000`
- `len(duration) == n`
- `1 <= duration[i] <= 10^9` for each valid `i`
- `0 <= len(prerequisites) <= 200000`
- Each prerequisite is a pair `[a, b]` with `0 <= a, b < n`
Examples
Input: (4, [3, 2, 4, 1], [[0, 2], [1, 2], [2, 3]])
Expected Output: ([3, 2, 7, 8], 8)
Explanation: Tasks 0 and 1 can run immediately, finishing at 3 and 2. Task 2 starts after both are done, so it starts at 3 and finishes at 7. Task 3 finishes at 8.
Input: (3, [5, 1, 2], [])
Expected Output: ([5, 1, 2], 5)
Explanation: With no prerequisites, all tasks run in parallel. Each task finishes after its own duration, and the total time is the maximum of those values.
Hints
- A valid schedule exists only if the prerequisite graph is a DAG. Think about using topological sorting to process tasks in dependency order.
- For each task, track the maximum completion time among all of its prerequisites. Its own earliest finish is that value plus its duration.