Task Dependency Resolver
In many real-world scenarios, tasks have dependencies. For instance, in software build systems, certain modules must be compiled before others. In project management, some activities can only begin after their prerequisites are met. Ensuring tasks are executed in a valid order is crucial to prevent deadlocks and ensure successful completion.
You are given a total number of tasks and a list of prerequisite pairs. Each task is labeled from 0 to numTasks - 1. A prerequisite pair [task, prerequisite] indicates that task cannot be started until prerequisite has been completed.
Your goal is to find one valid order in which all tasks can be completed. If it's impossible to complete all tasks due to a circular dependency (a cycle), you should indicate this.
findTaskOrder(numTasks: number, prerequisites: number[][]): number[]
numTasks: An integer representing the total number of tasks, labeled from 0 to numTasks - 1.prerequisites: An array of arrays, where each inner array [task, prerequisite] signifies that task depends on prerequisite. That is, prerequisite must be completed before task can begin.[].0 to numTasks - 1.numTasks is 0, an empty array [] should be returned as there are no tasks.prerequisites is an empty array, all tasks can be completed in any order (e.g., [0, 1, ..., numTasks - 1]). Your algorithm should produce one such valid order.Examples
Example 1
Input:
numTasks = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]
Output:
[0,1,2,3]
Note:
Task 0 has no prerequisites. Tasks 1 and 2 depend on 0. Task 3 depends on both 1 and 2. A valid order is to complete 0 first, then 1 and 2 (in any order), and finally 3.
Example 2
Input:
numTasks = 2, prerequisites = [[1,0], [0,1]]
Output:
[]
Note:
Task 1 depends on 0, and Task 0 depends on 1. This forms a circular dependency, making it impossible to complete both tasks. Thus, an empty array is returned.
Example 3
Input:
numTasks = 3, prerequisites = []
Output:
[0,1,2]
Note:
With no prerequisites, all tasks can be completed in any order. The solution might return them in numerical order or another valid permutation.
Constraints
0 <= numTasks <= 20000 <= prerequisites.length <= numTasks * (numTasks - 1)prerequisites[i] has length == 2.0 <= prerequisites[i][0], prerequisites[i][1] < numTasks[task, prerequisite] are unique.[0,0] will not be in prerequisites).Loading editor...