Task Order With Prerequisites
Problem statement
You have n tasks labeled from 0 to n - 1. Each prerequisites[i] = [a, b] means task a must finish before task b can start.
Return an order that runs all n tasks, one at a time, and respects every pair. A task is ready when all of the tasks it waits for have already run. Whenever more than one task is ready, run the one with the smallest label first. This rule makes the answer unique.
If no order can include every task, because some tasks wait on each other in a loop, return an empty array.
Function
findTaskOrder(n: int, prerequisites: int[][]) → int[]Examples
Example 1
n = 5prerequisites = [[3,1],[0,4],[3,0],[2,4]]return = [2,3,0,1,4]At the start, only tasks 2 and 3 wait for nothing. Run 2 first because it is smaller, then 3. Running 3 makes tasks 0 and 1 ready, so run 0. Task 4 waited for 0 and 2, so now both 1 and 4 are ready. Run 1, the smaller one, and then 4.
Example 2
n = 5prerequisites = [[3,0],[1,0],[4,2]]return = [1,3,0,4,2]At the start, tasks 1, 3 and 4 are ready. Run 1, then 3. Now both prerequisites of task 0 are done, so the ready tasks are 0 and 4. Run 0, then 4, and finally 2, which needed 4. Running every task that was ready at the start before any new one would give [1, 3, 4, 0, 2], which is a valid order but not the one asked for.
Example 3
n = 4prerequisites = [[0,1],[1,2],[2,1],[0,3]]return = []Task 1 must run before task 2, and task 2 must run before task 1. Neither can ever start, so no order can include all four tasks. Return an empty array, even though tasks 0 and 3 could run.
Constraints
1 <= n <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= prerequisites[i][0], prerequisites[i][1] <= n - 1prerequisites[i][0] != prerequisites[i][1]- No pair
[a, b]appears more than once.