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

难度: Medium

你被安排了 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

Submission

运行时间: 36 ms

内存: 16.0 MB

class Solution:
    def minSessions(self, tasks: List[int], t: int) -> int:
        n = len(tasks)
        tasks.sort(reverse=True)
        used = [0] * n  # 每个session所用时间
        cur = 0  # 已占用的session个数
        ans = n
        def dfs(i):
            nonlocal cur, ans
            if cur >= ans:
                return 
            if i == n:
                ans = cur
                return
            x = tasks[i]
            vis = 0
            for j in range(cur):
                if vis >> used[j] & 1:
                    continue
                vis |= 1 << used[j]
                if used[j] + x <= t:
                    used[j] += x
                    dfs(i+1)
                    used[j] -= x
            used[cur] += x
            cur += 1
            dfs(i+1)
            cur -= 1
            used[cur] -= x
        
        dfs(0)
        return ans

Explain

题解采用深度优先搜索（DFS）加剪枝的策略来找到最小的工作时间段数。首先，将任务按照所需时间的降序排序，以尝试优先处理耗时较长的任务。算法使用了一个数组 used 来跟踪每个时间段已用的总时间。通过递归地尝试将每个任务放入现有的或新的时间段，并检查这是否能够减少总的时间段数。剪枝发生在当前时间段数已经大于或等于已知的最小时间段数时，此时终止当前路径的搜索。该解决方案的关键是尝试所有可能的组合，并通过剪枝来优化搜索。

时间复杂度: O((cur + 1)^n)

空间复杂度: O(n)

class Solution:
    def minSessions(self, tasks: List[int], t: int) -> int:
        n = len(tasks)  # 任务数量
        tasks.sort(reverse=True)  # 降序排序任务
        used = [0] * n  # 每个session使用的时间
        cur = 0  # 当前已使用的session数量
        ans = n  # 初始化最少需要的session数为任务总数
        def dfs(i):
            nonlocal cur, ans
            if cur >= ans:  # 如果当前session数量已达到或超过已知最小值，剪枝
                return
            if i == n:  # 如果所有任务都已处理
                ans = cur  # 更新最小session数
                return
            x = tasks[i]  # 当前任务所需时间
            vis = 0  # 记录已尝试的时间配置，防止重复
            for j in range(cur):  # 尝试将当前任务放入已有的session
                if vis >> used[j] & 1:  # 如果当前配置已尝试过，跳过
                    continue
                vis |= 1 << used[j]  # 标记当前配置
                if used[j] + x <= t:  # 如果当前session有足够空间
                    used[j] += x  # 放入任务
                    dfs(i+1)  # 递归处理下一个任务
                    used[j] -= x  # 回溯
            used[cur] += x  # 尝试开启新的session
            cur += 1
            dfs(i+1)  # 递归处理下一个任务
            cur -= 1  # 回溯
            used[cur] -= x  # 回溯
        
        dfs(0)  # 从第一个任务开始DFS
        return ans  # 返回最小的session数量

Explore

在深度优先搜索（DFS）中，先尝试将任务放入已有的session是为了尽可能利用现有的时间段资源，从而减少创建新的session的需求。这种方法有助于尽早填满现有的session，避免过早地增加session数量，从而可能找到需要的最小session数量。此外，这种策略也是为了减少搜索空间，因为开启新的session意味着更多的分支，可能导致复杂度增加。

题解选择DFS加剪枝的方法，因为该问题是一个NP难题，涉及到如何将不同任务组合分配到尽可能少的session中，每个session的时间不超过给定限制。动态规划适用于问题具有明确的递推关系和较少的状态数时更为有效，但在本问题中，状态空间可能非常大，因为每个任务加入session的顺序和方式可以非常灵活。而贪心算法虽然实现简单，但不能保证找到全局最优解，只能保证每一步是局部最优。相比之下，DFS可以探索所有可能的任务分配方式，并通过剪枝有效地减少搜索空间，更有可能找到最优解。

在实现剪枝操作时，具体的判断方法包括：1. 当前使用的session数量已经达到或超过已知的最小session数量时，继续探索当前路径不太可能产生更优解，因此可以停止当前路径的搜索。2. 当前任务配置已经尝试过，可以通过位运算标记已尝试的配置，避免重复探索相同的配置，从而减少无效的搜索。这两种方法都是为了减少搜索过程中的冗余操作，加速寻找最优解的过程。