2021-12-05：刚入职网易互娱，新人mini项目便如火如荼的开展起来。为了更好的项目协作与管理

2021-12-05：刚入职网易互娱，新人mini项目便如火如荼的开展起来。为了更好的项目协作与管理， 小易决定将学到的甘特图知识用于mini项目时间预估。小易先把项目中每一项工作以任务的形式列举出来， 每项任务有一个预计花费时间与前置任务表，必须完成了该任务的前置任务才能着手去做该任务。 作为经验PM，小易把任务划分得井井有条，保证没有前置任务或者前置任务全数完成的任务，都可以同时进行。 小易给出了这样一个任务表，请作为程序的你计算需要至少多长时间才能完成所有任务。 输入第一行为一个正整数T，表示数据组数。 对于接下来每组数据，第一行为一个正整数N，表示一共有N项任务。 接下来N行，每行先有两个整数Di和Ki，表示完成第i个任务的预计花费时间为Di天，该任务有Ki个前置任务。 之后为Ki个整数Mj，表示第Mj个任务是第i个任务的前置任务。 数据范围：对于所有数据，满足1<=T<=3, 1<=N, Mj<=100000, 0<=Di<=1000, 0<=sum(Ki)<=N*2。 来自网易。

答案2021-12-07：

拓扑排序+实时更新。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    nums := [][]int{{1, 2, 3}, {4, 5, 6}}
    days := []int{2}
    headCount := []int{3}
    ret := dayCount(nums, days, headCount)
    fmt.Println(ret)
}

func dayCount(nums [][]int, days []int, headCount []int) int {
    //Queue<Integer> head = countHead(headCount);
    head := countHead(headCount)
    maxDay := 0
    //int[] countDay = new int[days.length];
    countDay := make([]int, len(days))
    for len(head) > 0 {
        cur := head[0]
        head = head[1:]
        countDay[cur] += days[cur]
        for j := 0; j < len(nums[cur]); j++ {
            headCount[nums[cur][j]]--
            if headCount[nums[cur][j]] == 0 {
                //head.offer(nums[cur][j]);
                head = append(head, nums[cur][j])
            }
            countDay[nums[cur][j]] = getMax(countDay[nums[cur][j]], countDay[cur])
        }
    }
    for i := 0; i < len(countDay); i++ {
        maxDay = getMax(maxDay, countDay[i])
    }
    return maxDay
}

func countHead(headCount []int) []int {
    //Queue<Integer> queue = new LinkedList<>();
    queue := make([]int, 0)
    for i := 0; i < len(headCount); i++ {
        if headCount[i] == 0 {
            //queue.offer(i); // 没有前驱任务
            queue = append(queue, i)
        }
    }
    return queue
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

左神java代码