Project Task Scheduling
In complex software development or project management, tasks often have intricate dependencies. For instance, 'implement feature X' might require 'design database schema Y' to be completed first. Efficiently scheduling these tasks is crucial for project success. This problem challenges you to determine a valid execution sequence for a set of project tasks, ensuring all prerequisites are met, or identify if such a sequence is impossible due to circular dependencies.
Implement the findTaskOrder function that takes the total number of tasks and their prerequisites as input. Your goal is to:
[task, prerequisite], prerequisite comes before task in the returned order.[].function findTaskOrder(n: number, prerequisites: number[][]): number[]
n: An integer representing the total number of tasks. Tasks are labeled from 0 to n-1.prerequisites: An array of pairs [task, prerequisite]. Each pair indicates that task cannot be started until prerequisite is completed. In graph terms, there's a directed edge from prerequisite to task.[].prerequisites is empty, any order of tasks 0 to n-1 is valid. For example, [0, 1, ..., n-1]. If n=0, an empty array [] should be returned.Examples
Example 1
Input:
n = 2, prerequisites = [[1,0]]
Output:
[0,1]
Note:
Task 0 has no prerequisites. Task 1 depends on Task 0. A valid order is [0, 1].
Example 2
Input:
n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output:
[0,1,2,3]
Note:
Task 0 has no prerequisites. Task 1 depends on 0. Task 2 depends on 0. Task 3 depends on 1 and 2. A valid order is [0, 1, 2, 3]. Another valid order would be [0, 2, 1, 3].
Example 3
Input:
n = 3, prerequisites = [[1,0],[0,1]]
Output:
[]
Note:
Task 1 depends on Task 0, and Task 0 depends on Task 1, forming a circular dependency. It's impossible to complete both tasks, so no valid order exists.
Constraints
1 <= n <= 10^50 <= prerequisites.length <= min(n * (n - 1) / 2, 10^5)prerequisite[i] is a pair [task_i, pre_i].0 <= task_i, pre_i < ntask_i != pre_i (A task cannot be its own prerequisite).[task, prerequisite] in prerequisites are unique.Loading editor...