Hard

题目描述

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

现在你有 k 个工人，你可以给他们分配工作。每项工作都应该分配给恰好一个工人。一个工人的工作时间是完成分配给他的所有工作花费时间的总和。你的目标是设计一个最优的分配方案，使得工人的最大工作时间得以最小化。

返回分配方案中工人的最大工作时间的最小值。

示例 1：

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每个工人分配一项工作，最大工作时间是 3 。

示例 2：

输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
工人 1：1, 2, 8（工作时间 = 1 + 2 + 8 = 11）
工人 2：4, 7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。

提示：

  • 1 <= k <= jobs.length <= 12
  • 1 <= jobs[i] <= 10^7

解题思路

这是一道经典的状态压缩动态规划问题。由于工作数量较小（≤12），我们可以用位掩码表示工作的分配状态。

核心思路：

  1. 状态压缩DP：用二进制掩码 mask 表示已完成的工作集合，dp[mask][j] 表示完成 mask 中的工作，使用 j 个工人时的最小最大工作时间
  2. 状态转移：对于当前状态 mask 和工人数 j，枚举当前工人可以承担的工作子集 subset，转移到状态 mask ^ subset 和工人数 j-1
  3. 子集枚举：对于状态 mask，我们需要枚举它的所有非空子集作为当前工人的工作分配

优化策略：

  • 预计算所有可能工作组合的总时间，避免重复计算
  • 使用位运算快速枚举子集：subset = (subset - 1) & mask
  • 从大到小枚举子集，优先尝试工作量大的分配

时间复杂度： O(3^n × k)，其中 n 是工作数量。这是因为对于每个状态 mask，我们需要枚举其所有子集，子集数量为 2^(popcount(mask))，总的状态转移数约为 3^n。

推荐解法： 状态压缩DP，代码简洁且效率较高。

代码实现

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size();
        vector<int> sum(1 << n);
        
        // 预计算所有子集的工作时间总和
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    sum[mask] += jobs[i];
                }
            }
        }
        
        // dp[mask][j] 表示完成mask中的工作，使用j个工人的最小最大工作时间
        vector<vector<int>> dp(1 << n, vector<int>(k + 1, INT_MAX));
        dp[0][0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int j = 1; j <= k && j <= __builtin_popcount(mask); j++) {
                // 枚举mask的所有非空子集
                for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {
                    int prev = mask ^ subset;
                    if (dp[prev][j - 1] != INT_MAX) {
                        dp[mask][j] = min(dp[mask][j], max(dp[prev][j - 1], sum[subset]));
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1][k];
    }
};

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        n = len(jobs)
        # 预计算所有子集的工作时间总和
        sum_jobs = [0] * (1 << n)
        for mask in range(1 << n):
            for i in range(n):
                if mask & (1 << i):
                    sum_jobs[mask] += jobs[i]
        
        # dp[mask][j] 表示完成mask中的工作，使用j个工人的最小最大工作时间
        dp = [[float('inf')] * (k + 1) for _ in range(1 << n)]
        dp[0][0] = 0
        
        for mask in range(1 << n):
            for j in range(1, min(k + 1, bin(mask).count('1') + 1)):
                # 枚举mask的所有非空子集
                subset = mask
                while subset > 0:
                    prev = mask ^ subset
                    if dp[prev][j - 1] != float('inf'):
                        dp[mask][j] = min(dp[mask][j], max(dp[prev][j - 1], sum_jobs[subset]))
                    subset = (subset - 1) & mask
        
        return dp[(1 << n) - 1][k]

public class Solution {
    public int MinimumTimeRequired(int[] jobs, int k) {
        int n = jobs.Length;
        int[] sum = new int[1 << n];
        
        // 预计算所有子集的工作时间总和
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum[mask] += jobs[i];
                }
            }
        }
        
        // dp[mask][j] 表示完成mask中的工作，使用j个工人的最小最大工作时间
        int[,] dp = new int[1 << n, k + 1];
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int popcount = System.Numerics.BitOperations.PopCount((uint)mask);
            for (int j = 1; j <= Math.Min(k, popcount); j++) {
                // 枚举mask的所有非空子集
                for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {
                    int prev = mask ^ subset;
                    if (dp[prev, j - 1] != int.MaxValue) {
                        dp[mask, j] = Math.Min(dp[mask, j], Math.Max(dp[prev, j - 1], sum[subset]));
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1, k];
    }
}

var minimumTimeRequired = function(jobs, k) {
    const n = jobs.length;
    const sum = 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)) {
                sum[mask] += jobs[i];
            }
        }
    }
    
    // dp[mask][j] 表示完成mask中的工作，使用j个工人的最小最大工作时间
    const dp = Array.from({length: 1 << n}, () => new Array(k + 1).fill(Infinity));
    dp[0][0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        const popcount = mask.toString(2).replace(/0/g, '').length;
        for (let j = 1; j <= Math.min(k, popcount); j++) {
            // 枚举mask的所有非空子集
            for (let subset = mask; subset > 0; subset = (subset - 1) & mask) {
                const prev = mask ^ subset;
                if (dp[prev][j - 1] !== Infinity) {
                    dp[mask][j] = Math.min(dp[mask][j], Math.max(dp[prev][j - 1], sum[subset]));
                }
            }
        }
    }
    
    return dp[(1 << n) - 1][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(3^n × k)
空间复杂度O(2^n × k)

其中 n 是工作数量。时间复杂度来源于对每个状态枚举其所有子集的操作，空间复杂度来源于 DP 数组的存储。

相关题目