2022-04-01：有n个人，m个任务，任务之间有依赖记录在int[][] depends里

2022-04-01：有n个人，m个任务，任务之间有依赖记录在int[][] depends里。 比如: depends[i] = [a, b]，表示a任务依赖b任务的完成， 其中 0 <= a < m，0 <= b < m， 1个人1天可以完成1个任务，每个人都会选当前能做任务里，标号最小的任务， 一个任务所依赖的任务都完成了，该任务才能开始做。 返回n个人做完m个任务，需要几天。 来自hulu。

答案2022-04-01：

拓扑排序。

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

package main

import (
	"fmt"
	"sort"
)

func main() {
	depends := [][]int{{3, 0}, {4, 1}, {5, 2}, {4, 3}, {6, 5}, {7, 4}, {7, 6}}
	ret := days(3, 8, depends)
	fmt.Println(ret)
	ret = days(2, 8, depends)
	fmt.Println(ret)
}

func days(n, m int, depends [][]int) int {
	if n < 1 {
		return -1
	}
	if m <= 0 {
		return 0
	}
	// nexts[0] = {1,4}
	nexts := nexts(depends, m)
	indegree := indegree(nexts, m)
	// 工人队列！
	workers := make([]int, 0)
	for i := 0; i < n; i++ {
		workers = append(workers, 0)
	}
	// zeroIn ： 放着工作，放着可以开始做的工作，不能做的任务，不在其中
	// 小根堆：标号小的任务，一定要先做！
	zeroIn := make([]int, 0)
	for i := 0; i < m; i++ {
		if indegree[i] == 0 {
			zeroIn = append(zeroIn, i)
		}
	}
	// start[i] ：i之前必须完成的任务，占了几天，导致i任务只能从那天开始！
	start := make([]int, m)
	// 完成所有任务的最大天数
	finishAll := 0
	done := 0
	for len(zeroIn) > 0 { // 有任务可做
		// 当前可以做的任务中，标号最小的任务
		sort.Ints(zeroIn)
		job := zeroIn[0]
		zeroIn = zeroIn[1:]
		// 当前可用的工人里，最早醒的！
		sort.Ints(workers)
		wake := workers[0]
		workers = workers[1:]
		// job 何时完成呢？
		// (工人醒来，开工时间)最晚的！+1
		finish := getMax(start[job], wake) + 1
		finishAll = getMax(finishAll, finish)
		done++
		// 消除影响
		for _, next := range nexts[job] {
			start[next] = getMax(start[next], finish)
			indegree[next]--
			if indegree[next] == 0 {
				zeroIn = append(zeroIn, next)
			}
		}
		workers = append(workers, finish)
	}
	if done == m {
		return finishAll
	} else {
		return -1
	}
}

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

func nexts(depends [][]int, m int) [][]int {
	//Arrays.sort(depends, (a, b) -> a[1] - b[1]);
	sort.Slice(depends, func(i, j int) bool {
		a := depends[i]
		b := depends[j]
		return a[1] < b[1]
	})
	n := len(depends)
	//int[][] nexts = new int[m][0];
	nexts := make([][]int, m)
	for i := 0; i < m; i++ {
		nexts[i] = make([]int, 0)
	}
	if n == 0 {
		return nexts
	}
	size := 1
	for i := 1; i < n; i++ {
		if depends[i-1][1] != depends[i][1] {
			from := depends[i-1][1]
			nexts[from] = make([]int, size)
			for k, j := 0, i-size; k < size; k, j = k+1, j+1 {
				nexts[from][k] = depends[j][0]
			}
			size = 1
		} else {
			size++
		}
	}
	from := depends[n-1][1]
	nexts[from] = make([]int, size)
	for k, j := 0, n-size; k < size; k, j = k+1, j+1 {
		nexts[from][k] = depends[j][0]
	}
	return nexts
}

func indegree(nexts [][]int, m int) []int {
	indegree := make([]int, m)
	for i := 0; i < m; i++ {
		for j := 0; j < len(nexts[i]); j++ {
			indegree[nexts[i][j]]++
		}
	}
	return indegree
}

执行结果如下：

左神java代码