给你一个整数数组 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 < high) {
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 < workloads.length; ++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 < k; 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)