m做的任务(m的任务项目表字母圈)

2023-12-15 19:06:34 游戏快问 204

m做的任务(m的任务项目表字母圈)

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 mainimport ("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 := 0done := 0for len(zeroIn) > 0 { // 有任务可做// 当前可以做的任务中，标号最小的任务sort.Ints(zeroIn)job := zeroIn[0]zeroIn = zeroIn[1:]// 当前可用的工人里，最早醒的！sort.Ints(workers)wake := workers[0]workers = workers[1:]// job 何时完成呢？// (工人醒来，开工时间)最晚的！+1finish := getMax(start[job], wake) + 1finishAll = 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 := 1for 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}

执行结果如下：

m做的任务(m的任务项目表字母圈)插图