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

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

给你一个整数数组 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

题解:

回溯法+剪枝

用一个 vector block 记录每个人分配到的工作量,尝试将一份工作分配给一个人,且它的工作时间不超过lim要求,之后开启递归分配下一项工作,尝试找到一个成功分配全部工作的路径

递归深度为 n=jobs.length 工作数量,每次递归需要检测范围为 k 员工数量并开启分支,最坏情况下走满树时间复杂度为 O(k^n)
题设 1 <= k <= jobs.length <= 12,最坏情况下 12^12 = 8.9E12,外面还套了一个二分,还要再乘 log12 = 3.xxxx,远超1s极限算量1E8

因此我们需要考虑一些剪枝的方法,首先我们可以 sort 一下 jobs ,时长从大到小开始分配,进而能够更快的超出限制,被剪枝掉,其次是朴素写法中存在很多重复的路径

例如对于第一份工作的分配,所有人工作时长全部是0,我们只需要分配一次

[t1,0,0,0,0]
之后的
[0,t1,0,0,0]
...

都是重复操作。

56号测试用例:

[5,5,4,4,4]
2

如果先将 5h 分配给两个人block [5,5],之后分配4时,只需要走一次 [9,5],后面的[5,9] 是重复操作

由于jobs已排序,因此我们每次枚举到的 block[i] 应当和上一次不一样,才是没走过的路径,进而排除全0时的重复放置,或是出现相同工作时长分配时的重复放置

class Solution {
public:
    int k;
    vector  block;
    bool backtracking(vector& jobs,int id,int lim) {
        if(id==-1) return true; //出口 全部放完了

        bool res=false;
        int last=INT_MIN; 

        for(int i=0;i& jobs, int k) {
        this->k = k;
        int s=0; //区间左端点(最小)
        int e=0; //区间右端点(最大)
        int m;//中间
        int n = jobs.size()-1;//起手下标
        block = vector(k,0); // 拷贝初始化
        sort(jobs.begin(),jobs.end());    
        s=jobs[n];//结果最小应是 jobs[i] 的最大值

        for(auto i : jobs) { //最大应是 sum(jobs.begin(),jobs.end()) 小心越界
            if(e<=INT_MAX-i) e+=i;
            else e=INT_MAX;
        }        
        while(s!=e) {
            int m = (s+e)/2;
            if(backtracking(jobs,n,m)) { //成功 尝试缩减区间
                e=m;//m无法排除
            }else {//失败 扩大
                s=m+1;//m肯定不对最少加1
            }
        }
        return s;
    }
};

   转载规则


《【Day12】1723.完成所有工作的最短时间》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录