难度 - >
困难
日期 - >
2021年5月08日
开始时间 - >
00:00
结束时间 - >
00:00
所用时间 - >
00分钟
执行用时 - >
00 ms
内存消耗 - >
00.- MB
给你一个整数数组 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`
class Solution {
int[] jobs;
int n, k;
int ans = 0x3f3f3f3f;
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
n = jobs.length;
k = _k;
int[] sum = new int[k];
dfs(0, 0, sum, 0);
return ans;
}
/**
* 【补充说明】不理解可以看看下面的「我猜你问」的 Q5 哦 ~
*
* u : 当前处理到那个 job
* used : 当前分配给了多少个工人了
* sum : 工人的分配情况 例如:sum[0] = x 代表 0 号工人工作量为 x
* max : 当前的「最大工作时间」
*/
void dfs(int u, int used, int[] sum, int max) {
if (max >= ans) return;
if (u == n) {
ans = max;
return;
}
// 优先分配给「空闲工人」
if (used < k) {
sum[used] = jobs[u];
dfs(u + 1, used + 1, sum, Math.max(sum[used], max));
sum[used] = 0;
}
for (int i = 0; i < used; i++) {
sum[i] += jobs[u];
dfs(u + 1, used, sum, Math.max(sum[i], max));
sum[i] -= jobs[u];
}
}
}