How does state transition dynamic programming apply to this problem?

State transition dynamic programming uses a bitmask to represent the set of tasks completed so far, allowing you to efficiently calculate the minimum work sessions needed.

What is bitmasking, and why is it important for this problem?

Bitmasking is a technique used to represent subsets of tasks in a compact form. It helps track which tasks have been assigned and ensures efficient calculation of task combinations.

Can I solve the "Minimum Number of Work Sessions to Finish the Tasks" problem using a greedy approach?

A greedy approach would not guarantee the optimal solution because it may not always make the best choices at each step. Dynamic programming is better suited for this problem.

How do I avoid redundant calculations in this problem?

Use memoization to store the results of previously computed task assignments, preventing redundant recalculations and improving performance.

What is the time complexity of the solution?

The time complexity is O(2^n), where n is the number of tasks, as you need to explore all subsets of tasks to find the optimal solution.

#1986

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个工作时间段中，你可以至多连续工作 sessionTime 个小时，然后休息一会儿。你需要按照如下条件完成给定任务：如果你在某一个时间段开始一个任务…

数组动态规划回溯位运算位掩码

题目描述

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

lightbulb

解题思路

方法一：状态压缩动态规划 + 枚举子集

我们注意到 $n$ 不超过 $14$ ，因此，我们可以考虑使用状态压缩动态规划的方法求解本题。

我们用一个长度为 $n$ 的二进制数 $i$ 来表示当前的任务状态，其中 $i$ 的第 $j$ 位为 $1$ ，当且仅当第 $j$ 个任务被完成。我们用 $f[i]$ 表示完成状态为 $i$ 的所有任务所需要的最少工作时间段数。

我们可以枚举 $i$ 的所有子集 $j$ ，其中 $j$ 的二进制表示中的每一位都是 $i$ 的二进制表示中对应位的子集，即 $j \subseteq i$ 。如果 $j$ 对应的任务可以在一个工作时间段内完成，那么我们可以用 $f[i \oplus j] + 1$ 来更新 $f[i]$ ，其中 $i \oplus j$ 表示 $i$ 和 $j$ 的按位异或。

最终的答案即为 $f[2^n - 1]$ 。

时间复杂度 $O(n \times 3^n)$ ，空间复杂度 $O(2^n)$ 。其中 $n$ 为任务的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        ok = [False] * (1 << n)
        for i in range(1, 1 << n):
            t = sum(tasks[j] for j in range(n) if i >> j & 1)
            ok[i] = t <= sessionTime
        f = [inf] * (1 << n)
        f[0] = 0
        for i in range(1, 1 << n):
            j = i
            while j:
                if ok[j]:
                    f[i] = min(f[i], f[i ^ j] + 1)
                j = (j - 1) & i
        return f[-1]

speed

复杂度分析

指标	值
时间	complexity depends on the number of subsets of tasks, which is 2^n, where n is the number of tasks. The space complexity depends on the memoization table, which stores results for each subset of tasks, making it O(2^n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of bitmasking and dynamic programming principles.
question_mark
Assess the candidate’s ability to optimize recursive solutions using memoization.
question_mark
Evaluate how well the candidate can balance brute force and optimization techniques.

warning

常见陷阱

外企场景

error
Failing to properly handle all combinations of task assignments within the session time.
error
Not using bitmasking effectively to track which tasks have been assigned.
error
Overlooking the importance of memoization, leading to redundant calculations and slower performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the maximum number of tasks or change the session time limit to test scalability.
arrow_right_alt
Use this problem as a foundation to solve similar problems involving scheduling and task assignments.
arrow_right_alt
Modify the problem to include different task durations and session time constraints.

help

常见问题

外企场景

继续练习

#1947 最大兼容性评分和 #1799 N 次操作后的最大分数和 #1723 完成所有工作的最短时间