1723.完成所有工作的最短时间

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

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二分 + 回溯

import java.util.Arrays;
class Solution {
private void sortReverse(int[] jobs) {
Arrays.sort(jobs);
int low = 0, high = jobs.length - 1;
while (low int temp = jobs[low];
jobs[low] = jobs[high];
jobs[high] = temp;
low++;
high--;
}
}
public int minimumTimeRequired(int[] jobs, int k) {
sortReverse(jobs);
int l = jobs[0], r = Arrays.stream(jobs).sum();
int ans = r;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(jobs, k, mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
public boolean check(int[] jobs, int k, int limit) {
int[] workloads = new int[k];
return backtrack(jobs, workloads, 0, limit);
}
public boolean backtrack(int[] jobs, int[] workloads, int i, int limit) {
if (i >= jobs.length) {
return true;
}
int cur = jobs[i];
for (int j = 0; j if (workloads[j] + cur <= limit) {
workloads[j] += cur;
if (backtrack(jobs, workloads, i + 1, limit)) {
return true;
}
workloads[j] -= cur;
}
// 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
// 或者当前工作恰能使该工人的工作量达到了上限
// 这两种情况下我们无需尝试继续分配工作
if (workloads[j] == 0 || workloads[j] + cur == limit) {
return false;
}
}
return false;
}
}


回溯

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, sum, 0);
return ans;
}
/**
* u : 当前处理到那个 job
* sum : 工人的分配情况 例如：sum[0] = x 代表 0 号工人工作量为 x
* max : 当前的「最大工作时间」
*/
void dfs(int u, int[] sum, int max) {
if (max >= ans) return;
if (u == n) {
ans = max;
return;
}
for (int i = 0; i sum[i] += jobs[u];
dfs(u + 1, sum, Math.max(sum[i], max));
sum[i] -= jobs[u];
}
}
}
作者：AC_OIer
链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/gong-shui-san-xie-yi-ti-shuang-jie-jian-4epdd/
来源：力扣（LeetCode）