← 返回 oracle 的题目列表Task Completion with Prerequisites
类型:online_judge
Given a set of tasks and their prerequisite tasks, determine the maximum number of tasks that can be completed.
Tasks can have prerequisite tasks, meaning the prerequisite task must be completed before starting the current task. If there is a cycle in the dependency chain, none of the tasks involved in the cycle can be completed.
Implement a function that takes the number of tasks n and a list of dependencies prerequisites, and returns the maximum number of tasks that can be completed.
Input:
n: an integer representing the number of tasks.
prerequisites: a 2D list where each element specifies a dependency, with prerequisites[i][0] depending on task prerequisites[i][1].
Output:
The maximum number of tasks that can be completed.
Example:
Input: n = 4, prerequisites = [[1, 0], [2, 1], [3, 2]]
Output: 4
Input: n = 2, prerequisites = [[1, 0], [0, 1]]
Output: 0
Constraints:
1 <= n <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= prerequisites[i][0], prerequisites[i][1] < n
Example
Input
4
[[1, 0], [2, 1], [3, 2]]