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.