第六章 - 高频考题(困难)
1723. 完成所有工作的最短时间

题目地址(1723. 完成所有工作的最短时间)

题目描述

给你一个整数数组 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] <= 107

前置知识

  • 位运算
  • 回溯
  • 剪枝
  • 子集枚举

公司

  • 暂无

方法一:二分 + 回溯 + 贪心 + 剪枝

思路

题目的解空间不难得出为 [max(jobs), sum(jobs)]。
因此可以使用能力检测二分来做。不熟悉能力检测二分的可以先看下我的二分专题,接下来套用最左二分模板即可。
需要注意的是能力检测 部分,我们需要枚举所有的情况,而不是像大多数能力检测二分那样直接一次遍历,这是因为这道题可以不连续 地选择多个 job。这提示我们使用回溯来解决。
初始化一个长度为 k 的 workloads, workloads[i] 表示第 i 个工人👷目前的工时。如果第 i 个工人可以做,就贪心地进行选择。否则,我们尝试下一个 job。
除此之外,我们需要对算法进行剪枝,否则无法通过所有的测试用例。
  • 剪枝 1:优先选择时间长的任务,这样在很多情况下可以有效减少递归的深度,尤其是短任务较多的情况。
  • 剪枝 2:如果某一个任务太大,直接超过了 limit,我们可以提前退出,因此不可能存在一种可行解。

关键点

  • 剪枝(否则会超时)

代码

  • 语言支持:Python3
class Solution:
def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
def backtrack(pos, workloads, limit):
if pos >= len(jobs): return True
for i in range(len(workloads)):
workload = workloads[i]
if jobs[pos] + workload <= limit:
workloads[i] += jobs[pos]
if backtrack(pos + 1, workloads, limit): return True
workloads[i] -= jobs[pos]
# 剪枝
if workload == 0:
return False
return False
def possible(limit):
return backtrack(0, [0] * k, limit)
# 剪枝
jobs.sort(reverse=True)
l, r = jobs[0], sum(jobs)
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l

方法二:状压 DP

思路

回溯和状压 DP 很多时候会一起出现。
这道题的数据范围提示我可能使用状压 DP,因此数据范围很小。通常这种情况,就是直接对数据范围很小的那个变量做状态压缩,用 n 位的数字来表示选取情况,并且一般 n 不会超过 20。
定义 dp[i][j] 表示使用 i 个 工人,完成任务情况如 j 所表示的最小的最大工作时间。
其中 j 就是一个 n 位的二进制数,其中 n 为 jobs 长度。数字上第 k 二进制位为 1 表示选取任务 k,否则表示不选取任务 k。
那么转移方程为:
其中 sub 是 j 的子集, sum(sub) 指的是任务情况如 sub 二进制表示那样的完成的总时间
因此我们必须枚举所有 j 的子集 sub。这里枚举子集可进行子集枚举优化策略,具体可看我的 91 天学算法的《基础篇 - 枚举》部分的讲义 。
提示:
这种子集枚举的题目,推荐使用 C++。如果使用 Python,则很可能会超时。

代码

  • 语言支持:C++,Python3
C++ Code:
class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
vector<int> sum(1 << n);
for (int i = 0; i < (1 << n); i++) {
for(int j = 0; j < n; j++) {
if (i & (1 << j)) {
sum[i] += jobs[j];
}
}
}
vector<vector<int>> dp(k, vector<int>(1 << n));
for (int i = 0; i < (1 << n); i++) {
dp[0][i] = sum[i];
}
for (int i = 1; i < k; i++) {
// 二进制子集枚举优化
for (int j = 0; j < (1 << n); j++) {
dp[i][j] = INT_MAX;
for (int x = j; x; x = (x - 1) & j) {
dp[i][j] = min(dp[i][j], max(dp[i - 1][j - x], sum[x]));
}
}
}
return dp[k - 1][(1 << n) - 1];
}
};
Python3 Code(超时):
class Solution:
def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
n = len(jobs)
sum_jobs = [0] * (1 << n)
dp = [[float("inf") for _ in range(1 << n)] for _ in range(k)]
for i in range(1 << n):
for j in range(n):
if i & 1 << j:
sum_jobs[i] += jobs[j]
for i in range(1 << n):
dp[0][i] = sum_jobs[i]
for i in range(1, k):
# 二进制子集枚举优化
for j in range(1 << n):
sub = j
while sub != 0:
dp[i][j] = min(dp[i][j], max(dp[i - 1][j - sub], sum_jobs[sub]))
sub = j & (sub - 1)
return dp[-1][-1]
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(2^n)$
  • 空间复杂度:$O(2^n)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。