题目描述
某分布式任务调度系统有 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
提示样例 2
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2021. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
* 只能import Go标准库
*/
package main
import (
"fmt"
)
// 待实现函数，在此函数中填入答题代码
func getMinTime(taskNum int, relations [][]int) int {
var timeList = make([][]int, taskNum+1)
for _, r := range relations {
sub := r[0]
master := r[1]
timeList[sub] = append(timeList[sub], master)
}
var resList = make(map[int]int)
var res int
for sub := range timeList {
if sub == 0 {
continue
}
temp := getTaskTime(timeList, sub, resList)
if temp > res {
res = temp
}
}
return res
}
func getTaskTime(timeList [][]int, key int, resList map[int]int) int {
// 已经计算过，不用再计算了
if resList[key] != 0 {
return resList[key]
}
if len(timeList[key]) == 0 {
resList[key] = 1
return 1
}
for _, master := range timeList[key] {
resTemp := getTaskTime(timeList, master, resList)
if resTemp > resList[key] {
resList[key] = resTemp
}
}
resList[key] = resList[key] + 1
return resList[key]
}
func main() {
taskNum := 9
relations := [][]int{{1, 2}, {2, 3}, {2, 4}, {4, 5}, {6, 4}, {8, 7}}
result := getMinTime(taskNum, relations)
fmt.Println(result)
}