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

解题思路

这是一个经典的状态压缩动态规划问题。由于任务数量最多只有14个，我们可以使用位掩码来表示任务的完成状态。

思路分析：

  1. 状态表示：使用 dp[mask] 表示完成状态为 mask 的所有任务所需的最少工作时间段数。其中 mask 是一个二进制数，第 i 位为 1 表示第 i 个任务已完成。

  2. 预处理：首先预处理所有可能的任务子集，计算每个子集的总时间。如果某个子集的总时间不超过 sessionTime，说明这些任务可以在一个工作时间段内完成。

  3. 状态转移：对于每个状态 mask，我们枚举所有可以在一个工作时间段内完成的任务子集 subset。如果 subset 是 mask 的子集，那么我们可以从状态 mask ^ subset（去掉这些任务后的状态）转移到状态 mask。

  4. 优化：为了避免重复计算，我们可以按照状态的二进制表示从小到大进行动态规划。

算法流程：

  • 预处理所有可能的任务组合，记录能在一个session内完成的组合
  • 使用状态压缩DP，dp[mask]表示完成mask状态下的任务所需最少session数
  • 对每个状态，尝试所有可能的单session任务组合进行转移
  • 最终答案为dp[(1<<n)-1]

时间复杂度虽然是指数级，但由于n≤14，实际运行效率可以接受。

代码实现

class Solution {
public:
    int minSessions(vector<int>& tasks, int sessionTime) {
        int n = tasks.size();
        vector<int> sessionSums(1 << n, 0);
        
        // 预计算每个子集的总时间
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    sessionSums[mask] += tasks[i];
                }
            }
        }
        
        // 找出所有可以在一个session内完成的任务组合
        vector<int> validSessions;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (sessionSums[mask] <= sessionTime) {
                validSessions.push_back(mask);
            }
        }
        
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == INT_MAX) continue;
            
            for (int session : validSessions) {
                // 只处理当前状态中未完成的任务
                int validTasks = session & (~mask);
                if (validTasks > 0) {
                    dp[mask | validTasks] = min(dp[mask | validTasks], dp[mask] + 1);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        
        # 预计算每个子集的总时间
        session_sums = [0] * (1 << n)
        for mask in range(1 << n):
            for i in range(n):
                if mask & (1 << i):
                    session_sums[mask] += tasks[i]
        
        # 找出所有可以在一个session内完成的任务组合
        valid_sessions = []
        for mask in range(1 << n):
            if session_sums[mask] <= sessionTime:
                valid_sessions.append(mask)
        
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
            
            for session in valid_sessions:
                # 只处理当前状态中未完成的任务
                valid_tasks = session & (~mask)
                if valid_tasks > 0:
                    new_mask = mask | valid_tasks
                    dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
        
        return dp[(1 << n) - 1]

public class Solution {
    public int MinSessions(int[] tasks, int sessionTime) {
        int n = tasks.Length;
        int[] sessionSums = new int[1 << n];
        
        // 预计算每个子集的总时间
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sessionSums[mask] += tasks[i];
                }
            }
        }
        
        // 找出所有可以在一个session内完成的任务组合
        List<int> validSessions = new List<int>();
        for (int mask = 0; mask < (1 << n); mask++) {
            if (sessionSums[mask] <= sessionTime) {
                validSessions.Add(mask);
            }
        }
        
        int[] dp = new int[1 << n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == int.MaxValue) continue;
            
            foreach (int session in validSessions) {
                // 只处理当前状态中未完成的任务
                int validTasks = session & (~mask);
                if (validTasks > 0) {
                    int newMask = mask | validTasks;
                    dp[newMask] = Math.Min(dp[newMask], dp[mask] + 1);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

var minSessions = function(tasks, sessionTime) {
    const n = tasks.length;
    const sessionSums = new Array(1 << n).fill(0);
    
    // 预计算每个子集的总时间
    for (let mask = 0; mask < (1 << n); mask++) {
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                sessionSums[mask] += tasks[i];
            }
        }
    }
    
    // 找出所有可以在一个session内完成的任务组合
    const validSessions = [];
    for (let mask = 0; mask < (1 << n); mask++) {
        if (sessionSums[mask] <= sessionTime) {
            validSessions.push(mask);
        }
    }
    
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(3^n)
空间复杂度O(2^n)

时间复杂度：预处理需要 O(n * 2^n)，主要的DP过程中，对于每个状态mask，我们需要枚举所有valid sessions，这在最坏情况下是 O(3^n)。 空间复杂度：需要存储 2^n 个状态的DP值和预处理数组。

相关题目