题目描述
某分布式任务调度系统有 taskNum 个任务(编号从 1 到 taskNum)需要调度,调度策略:
任务之间可能存在依赖关系,且无循环依赖,如任务1 依赖任务2,那么要等待任务2执行完才能执行任务1;
如果任务之间没有依赖关系,则可以并发执行(假设并发所需资源是充足的)。
现给出任务间的依赖关系,并假设每个任务的执行时间恒为 1 分钟,请计算执行完这 taskNum 个任务所需的最短时间(单位分钟)。
解答要求
时间限制:2000ms, 内存限制:256MB
输入
第一行为任务的数量 taskNum ,其值范围为:[1, 1000]
第二行为依赖关系的数量 relationsNum ,其值范围:[0, 500000]
接下来 relationsNum 行,每行描述一个依赖关系,格式为 IDi>IDj,表示任务 i 依赖任务 j ,IDi 和 IDj 值的范围为:[1, taskNum]
输出
一个整数,代表执行完所有任务的最短时间。
样例
输入样例 1
3
1
1>2
输出样例 1
2
提示样例 1
总共三个任务,任务1依赖任务2,任务2、任务3可以并发执行,最后执行任务1,最短时间为2分钟。
输入样例 2
9
6
1>2
2>3
2>4
4>5
6>4
8>7
输出样例 2
4
Java算法源码
import java.nio.charset.StandardCharsets;
import jav