class Solution {
public:
int minSessions(vector<int>& tasks, int sessionTime) {
}
};
1986. 完成任务的最少工作时间段
你被安排了 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.length1 <= n <= 141 <= tasks[i] <= 10max(tasks[i]) <= sessionTime <= 15原站题解
python3 解法, 执行用时: 864 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-26 17:50:16
class Solution:
def minSessions(self, tasks: List[int], sessionTime: int) -> int:
"""
f[mask]表示选取状态为mask时，所用最短时间
枚举mask中为1的位置i,置0后记为mask\i，f[mask]取枚举过程中的最小值
如果f[mask\i] % sessionTime + tasks[i] <= sessionTime: 那么就可以合在一个时间段完成
否则，需要新开时间段，这段剩下的时间记得加上去
"""
n = len(tasks)
f = [float('inf')] * (1 << n)
f[0] = 0
for mask in range(1, 1 << n):
for i in range(n):
if mask & (1 << i):
t = f[mask ^ (1 << i)]
cur = t % sessionTime
if cur + tasks[i] <= sessionTime:
f[mask] = min(f[mask], t + tasks[i])
else:
f[mask] = min(f[mask], t - cur + sessionTime + tasks[i])
return (f[(1 << n) - 1] + sessionTime - 1) // sessionTime
python3 解法, 执行用时: 4116 ms, 内存消耗: 72.4 MB, 提交时间: 2023-07-26 17:48:31
class Solution:
def minSessions(self, tasks: List[int], sessionTime: int) -> int:
L = len(tasks)
targetState = (1 << L) - 1
# 定义函数dfs(state, n),其中state表示tasks的完成状态，n表示还可以连续
# 工作的时间
@cache
def dfs(state, n):
if state == targetState: return 0
# 贪心：只有当剩余连续工作时间无法完成任何待完成工作时才休息(压榨自己)
if n < min(filter(lambda s: state >> s[0] & 1 == 0, enumerate(tasks)))[1]:
return 1 + dfs(state, sessionTime)
# 枚举可做的工作，从所有先做方案中取最小结果
return min(dfs(state | (1 << i), n - t) for i, t in enumerate(tasks) if state >> i & 1 == 0 and t <= n)
return 1 + dfs(0, sessionTime)