题目描述
给你一个整数数组 jobs
,其中 jobs[i]
是完成第 i
项工作要花费的时间。
请你将这些工作分配给 k
位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
样例
输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3 。
输入: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
算法分析
题目等价于将 n
份工作分成 k
个组,求每个组总时间的最小值。其中n
的大小是最多是12
,因此可以使用爆搜,把所有情况搜出来。搜索情况类似 小猫爬山
dfs(u, cnt, val)
:代表当前枚举到第u
份工作,一共开了cnt
个集合,开出的集合当前最大的总时间是val
枚举顺序:
-
第
u
份工作往第0
个集合中放 -
第
u
份工作往第1
个集合中放 -
…
-
第
u
份工作往第k
个集合中放 -
新开一个集合,第
u
份工作往第k + 1
个集合中放
时间复杂度
不好分析
Java 代码
class Solution {
static int[] s = new int[13];
static int[] jobs;
static int ans;
static int k;
static void dfs(int u, int cnt, int val)
{
if(val >= ans) return ;//剪枝
if(u == jobs.length)
{
ans = val;
return ;
}
for(int i = 0;i < cnt;i ++)
{
s[i] += jobs[u];
dfs(u + 1, cnt, Math.max(val, s[i]));
s[i] -= jobs[u];
}
//新开一个集合
if(cnt < k)
{
s[cnt] = jobs[u];
dfs(u + 1, cnt + 1, Math.max(val, s[cnt]));
s[cnt] = 0;
}
}
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
k = _k;
ans = 1000000000;
dfs(0, 0, 0);
return ans;
}
}
为什么取到答案的时候可以保证所有的工人都被分配到了工作呢?
没有保证所有的工人都被分配到了工作,将
u
个工作分配不超过k
个组(即k
个工人),满足这条件下把所有情况列出来取最佳题目贴错位置了?
改回来了,刚比赛完没有题号,只能看页数编,可能后面页数变了hh