leetcode1986_go_完成任务的最少工作时间段

题目

你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。

一个工作时间段中，你可以至多连续工作 sessionTime 个小时，然后休息一会儿。

你需要按照如下条件完成给定任务：

如果你在某一个时间段开始一个任务，你需要在同一个时间段完成它。

完成一个任务后，你可以立马开始一个新的任务。

你可以按任意顺序完成任务。

给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的最少数目的工作时间段。

测试数据保证 sessionTime 大于等于 tasks[i] 中的最大值。

示例 1：输入：tasks = [1,2,3], sessionTime = 3 输出：2

解释：你可以在两个工作时间段内完成所有任务。

- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。

- 第二个工作时间段：完成第三个任务，花费 3 小时。

示例 2：输入：tasks = [3,1,3,1,1], sessionTime = 8 输出：2

解释：你可以在两个工作时间段内完成所有任务。

- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。

- 第二个工作时间段，完成最后一个任务，花费 1 小时。

示例 3：输入：tasks = [1,2,3,4,5], sessionTime = 15 输出：1

解释：你可以在一个工作时间段以内完成所有任务。

提示：n == tasks.length

1 <= n <= 14

1 <= tasks[i] <= 10

max(tasks[i]) <= sessionTime <= 15

解题思路分析

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

func minSessions(tasks []int, sessionTime int) int {
   n := len(tasks)
   total := 1 << n          // 总的状态数
   dp := make([]int, total) // dp[i] => 任务状态为i时的最少工作时间
   for i := 0; i < total; i++ {
      dp[i] = n // 最多n次
   }
   dp[0] = 0
   sum := make([]int, total) // 枚举任务所有状态的和
   for i := 0; i < n; i++ {
      count := 1 << i
      for j := 0; j < count; j++ {
         sum[count|j] = sum[j] + tasks[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
      }
   }
   for i := 0; i < total; i++ {
      for j := i; j > 0; j = (j - 1) & i { // 遍历得到比较小的子集：数字i二进制为1位置上的非0子集
         if sum[j] <= sessionTime {
            dp[i] = min(dp[i], dp[i^j]+1) // 取补集-异或操作：取dp[i^j]+1操作最小值
         }
      }
   }
   return dp[total-1]
}

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

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

func minSessions(tasks []int, sessionTime int) int {
   n := len(tasks)
   total := 1 << n          // 总的状态数
   dp := make([]int, total) // dp[i] => 任务状态为i时的最少工作时间
   for i := 0; i < total; i++ {
      dp[i] = n // 最多n次
   }
   dp[0] = 0
   valid := make([]bool, total) // 状态是否<=sessionTime
   for i := 1; i < total; i++ { // 枚举状态
      sum := 0 // 该状态和
      for j := 0; j < n; j++ {
         if i&(1< 0 {
            sum = sum + tasks[j]
         }
      }
      if sum <= sessionTime {
         valid[i] = true
      }
   }

   for i := 1; i < total; i++ { // 枚举状态
      for j := i; j > 0; j = (j - 1) & i { // 遍历得到比较小的子集：数字i二进制为1位置上的非0子集
         if valid[j] == true {
            dp[i] = min(dp[i], dp[i^j]+1) // 取补集-异或操作：取dp[i^j]+1操作最小值
         }
      }
   }
   return dp[total-1]
}

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

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

func minSessions(tasks []int, sessionTime int) int {
   n := len(tasks)
   total := 1 << n          // 总的状态数
   dp := make([]int, total) // dp[i] => 任务状态为i时的最少工作时间
   for i := 0; i < total; i++ {
      dp[i] = n // 最多n次
   }
   dp[0] = 0
   sum := make([]int, total) // 枚举任务所有状态的和
   for i := 0; i < n; i++ {
      count := 1 << i
      for j := 0; j < count; j++ {
         sum[count|j] = sum[j] + tasks[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
      }
   }
   for i := 0; i < total; i++ {
      for j := 1; j <= i; j++ { // 暴力枚举子集
         if i|j == i && sum[j] <= sessionTime {
            dp[i] = min(dp[i], dp[i^j]+1) // 取补集-异或操作：取dp[i^j]+1操作最小值
         }
      }
   }
   return dp[total-1]
}

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

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

var res int

func minSessions(tasks []int, sessionTime int) int {
   res = len(tasks)
   dfs(tasks, sessionTime, 0, 0, make([]int, len(tasks)))
   return res
}

func dfs(tasks []int, sessionTime int, index, count int, arr []int) {
   if count >= res {
      return
   }
   if index == len(tasks) {
      res = count
      return
   }
   flag := false
   for i := 0; i < len(tasks); i++ { // 尝试每个工作段
      if arr[i] == 0 && flag == true { // 使用1个新的工作段即可
         break
      }
      if arr[i]+tasks[index] > sessionTime { // 当前超时，跳过尝试新的工作段
         continue
      }
      if arr[i] == 0 {
         flag = true
      }
      arr[i] = arr[i] + tasks[index]
      if flag == true {
         dfs(tasks, sessionTime, index+1, count+1, arr) // 有使用新的工作段
      } else {
         dfs(tasks, sessionTime, index+1, count, arr) // 没有使用新的工作段
      }
      arr[i] = arr[i] - tasks[index]
   }
}

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

func minSessions(tasks []int, sessionTime int) int {
   sort.Slice(tasks, func(i, j int) bool {
      return tasks[i] > tasks[j]
   })
   left, right := 1, len(tasks)

   for left < right {
      mid := left + (right-left)/2
      arr := make([]int, mid)
      if dfs(tasks, sessionTime, 0, mid, arr) == true {
         right = mid
      } else {
         left = mid + 1
      }
   }
   return left
}

func dfs(tasks []int, sessionTime int, index, count int, arr []int) bool {
   if index == len(tasks) { // 到最后退出
      return true
   }
   flag := false
   for i := 0; i < count; i++ { // 遍历每个工作段
      if arr[i] == 0 && flag == true { // 使用1个新的工作段即可
         break
      }
      if arr[i]+tasks[index] > sessionTime { // 当前超时，跳过尝试新的工作段
         continue
      }
      if arr[i] == 0 {
         flag = true
      }
      arr[i] = arr[i] + tasks[index]
      if dfs(tasks, sessionTime, index+1, count, arr) == true {
         return true
      }
      arr[i] = arr[i] - tasks[index]
   }
   return false
}