Topological Sort for Task Scheduling
Difficulty: Medium · Topics: Graph, Topological Sort, BFS · Acceptance: 100.0% of 1 submissions
Difficulty: Medium | Tags: Graph, BFS, Topological Sort
Description
Given n tasks labeled 0 to n-1 and a list of dependencies [a, b] (meaning task b must finish before task a), return a valid order to complete all tasks — or indicate that it's impossible (cycle detected).
Implement:
taskSchedule(numTasks, dependencies) → int[]
Examples
Example 1:
Input: numTasks = 4, deps = [[1,0], [2,0], [3,1], [3,2]]
Output: [0, 1, 2, 3] or [0, 2, 1, 3]
Example 2 — Impossible:
Input: numTasks = 2, deps = [[0,1], [1,0]]
Output: [] (cycle detected)
Example 3 — No dependencies:
Input: numTasks = 3, deps = []
Output: [0, 1, 2] (or any order)
Constraints
1 <= numTasks <= 20000 <= dependencies.length <= 5000- No duplicate edges.
Hints
Hint 1
Classic topological sort. Use Kahn's algorithm with in-degree counting and BFS queue.