Compute minimal time to finish dependent tasks
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Coding: Task Scheduling With Prerequisites (Parallel Allowed)
You have `n` tasks labeled `1..n`. Each task takes **exactly 1 unit of time** to complete. Some tasks have prerequisites.
You are given a list of prerequisite pairs `deps`, where each pair `[a, b]` means:
- Task `a` must be completed **before** task `b` can start.
You can run **any number of tasks in parallel** as long as their prerequisites are satisfied.
### Input
- Integer `n`.
- 2D array/list `deps` of pairs `[a, b]`.
### Output
Return the **minimum total time** (number of time units) required to finish all tasks.
### Notes
- If the dependency graph contains a cycle (tasks cannot be completed), specify what you would return (e.g., `-1`) and implement accordingly.
### Example
If `n = 3` and `deps = [[1,3],[2,3]]`, tasks 1 and 2 can run in parallel in time 1, then task 3 runs in time 2, so the answer is 2.
Quick Answer: This question evaluates understanding of graph algorithms and scheduling, specifically reasoning about task dependencies, parallel execution, and cycle detection in directed graphs.
Tasks 1..n each take one unit. deps [a,b] means a before b. Unlimited parallelism is allowed. Return the minimum total time, or -1 if there is a cycle.
Constraints
- Tasks are labeled 1..n
Examples
Input: (3, [[1, 3], [2, 3]])
Expected Output: 2
Input: (4, [[1, 2], [2, 3], [1, 3]])
Expected Output: 3
Hints
- The answer is the longest path length in the DAG.