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代码
