leetcode1723_go_完成所有工作的最短时间

题目

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。

工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化。

返回分配方案中尽可能最小的最大工作时间。

示例 1：输入：jobs = [3,2,3], k = 3 输出：3

解释：给每位工人分配一项工作，最大工作时间是 3 。

示例 2：输入：jobs = [1,2,4,7,8], k = 2 输出：11

解释：按下述方式分配工作：

1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）

2 号工人：4、7（工作时间 = 4 + 7 = 11）

最大工作时间是 11 。

提示：1 <= k <= jobs.length <= 12

1 <= jobs[i] <= 107

解题思路分析

1、二分查找+回溯；时间复杂度O(log(n)n^n)，空间复杂度O(n)

func minimumTimeRequired(jobs []int, k int) int {
   sort.Slice(jobs, func(i, j int) bool {
      return jobs[i] > jobs[j]
   })
   sum := 0
   for i := 0; i < len(jobs); i++ {
      sum = sum + jobs[i]
   }
   left, right := jobs[0], sum
   for left < right {
      mid := left + (right-left)/2
      if dfs(jobs, make([]int, k), mid, 0) {
         right = mid
      } else {
         left = mid + 1
      }
   }
   return left
}

func dfs(jobs []int, arr []int, limit int, index int) bool {
   if index >= len(jobs) {
      return true
   }
   for i := 0; i < len(arr); i++ {
      if arr[i]+jobs[index] <= limit {
         arr[i] = arr[i] + jobs[index]
         if dfs(jobs, arr, limit, index+1) == true {
            return true
         }
         arr[i] = arr[i] - jobs[index]
      }
      // 当前没有被分配 | 当前分配达到上线 => 不需要尝试继续分配
      // 剪枝:去除也可以过
      if arr[i] == 0 || arr[i]+jobs[index] == limit {
         break
      }
   }
   return false
}

2、二分查找+内置函数+回溯；时间复杂度O(log(n)n^n)，空间复杂度O(n)

func minimumTimeRequired(jobs []int, k int) int {
   sort.Slice(jobs, func(i, j int) bool {
      return jobs[i] > jobs[j]
   })
   sum := 0
   for i := 0; i < len(jobs); i++ {
      sum = sum + jobs[i]
   }
   left, right := jobs[0], sum
   return left + sort.Search(right-left, func(limit int) bool {
      return dfs(jobs, make([]int, k), limit+left, 0)
   })
}

func dfs(jobs []int, arr []int, limit int, index int) bool {
   if index >= len(jobs) {
      return true
   }
   for i := 0; i < len(arr); i++ {
      if arr[i]+jobs[index] <= limit {
         arr[i] = arr[i] + jobs[index]
         if dfs(jobs, arr, limit, index+1) == true {
            return true
         }
         arr[i] = arr[i] - jobs[index]
      }
      // 当前没有被分配 | 当前分配达到上线 => 不需要尝试继续分配
      // 剪枝:去除也可以过
      if arr[i] == 0 || arr[i]+jobs[index] == limit {
         break
      }
   }
   return false
}

3、动态规划+状态压缩；时间复杂度O(n*3^n)，空间复杂度O(n*2^n)

func minimumTimeRequired(jobs []int, k int) int {
   n := len(jobs)
   total := 1 << n
   sum := make([]int, total)
   for i := 0; i < n; i++ { // 预处理：任务的状态和，分配给某一个人的和
      count := 1 << i
      for j := 0; j < count; j++ {
         sum[count|j] = sum[j] + jobs[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
      }
   }
   dp := make([][]int, k) // f[i][j]=>给前i个人分配工作，工作的分配情况为j时，完成所有工作的最短时间
   for i := 0; i < k; i++ {
      dp[i] = make([]int, total)
   }
   for i := 0; i < total; i++ { // 第0个人的时候
      dp[0][i] = sum[i]
   }
   for i := 1; i < k; i++ {
      for j := 0; j < total; j++ {
         minValue := math.MaxInt32            // dp[i][j]未赋值，为0
         for a := j; a > 0; a = (a - 1) & j { // 遍历得到比较小的子集：数字j二进制为1位置上的非0子集
            // 取子集的补集：j-a 或者 使用异或j^a
            // minValue = min(minValue, max(dp[i-1][j-a], sum[a]))
            minValue = min(minValue, max(dp[i-1][j^a], sum[a]))
         }
         dp[i][j] = minValue
      }
   }
   return dp[k-1][total-1]
}

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

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

4、回溯；时间复杂度O(n^n)，空间复杂度O(n)

var res int

func minimumTimeRequired(jobs []int, k int) int {
   res = math.MaxInt32
   dfs(jobs, make([]int, k), 0, 0, 0)
   return res
}

// index => job的下标；count => 已经分配工人数组的个数
func dfs(jobs []int, arr []int, index int, maxValue int, count int) {
   if maxValue > res { // 剪枝
      return
   }
   if index == len(jobs) {
      res = maxValue
      return
   }
   if count < len(arr) { // 分配给空闲的
      arr[count] = jobs[index]
      dfs(jobs, arr, index+1, max(maxValue, arr[count]), count+1)
      arr[count] = 0
   }
   for i := 0; i < count; i++ { // 分配给非空闲的
      arr[i] = arr[i] + jobs[index]
      dfs(jobs, arr, index+1, max(maxValue, arr[i]), count)
      arr[i] = arr[i] - jobs[index]
   }
}

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