Compute minimal time to finish dependent tasks

Q: Compute minimal time to finish dependent tasks

This question evaluates understanding of graph algorithms and scheduling, specifically reasoning about task dependencies, parallel execution, and cycle detection in directed graphs.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.