做网站设计的广告公司,老外做中文网站,濮阳网站关键词,可以免费做简历的网站给你一个整数数组 jobs #xff0c;其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人#xff0c;且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作…给你一个整数数组 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. 二分
对于最小 的 最大工作时间进行二分搜索同时限定搜索的区间[时间最长的工作所有工作的总时间]右边界为所有工作的总时间一个人干完所有的活时间最长的工作即使在最好的情况下也要花费这个工作的时间
因为golang的sort.Search函数搜索的区间是[0,n),因此需要修改二分的代码 l sort.Search(r-l, func(limit int) bool {limitl2. 剪枝 if lojobs[cur]limit || load[i]0{break}两种情况需要剪枝 在将cur号工作分配给i号工人时递归下去无法找到满足条件的解情况下即bc(cur1)为false的情况如果是true就直接return了 当前的工人要完成这个工作的话刚刚等于限定的工作时间 当前工人没被分配工作load[i]0 当前的工人即使分配了工作的情况下都不能满足条件了。如果load[i]0就是这次不干活了活就要给其他人干需要的时间就更长了那就更不可能完成任务了
3. 回溯
从大到小递归遍历每一项工作时间在一次递归中尝试将当前工作分配给每个工人维护一个保存工人工作时间的数组然后开启层递归下一个工作如果不满足条件则回溯数组直到工作都分配完。
代码
func minimumTimeRequired(jobs []int, k int) int {sort.Sort(sort.Reverse(sort.IntSlice(jobs)))l,r:jobs[0],0for _, job : range jobs {rjob}return l sort.Search(r-l, func(limit int) bool {limitlload : make([]int, k)var bc func(cur int) boolbc func(cur int) bool{if curlen(jobs){return true}for i, lo : range load {if lojobs[cur]limit{load[i]jobs[cur]if bc(cur1){return true}load[i]-jobs[cur]}if lojobs[cur]limit || load[i]0{break}}return false}return bc(0)})
}
