【5.8】LeetCode每日一题·完成所有工作的最短时间

2021年05月08日 11时39分

标签： LeetCode 动态规划二分

## 题目描述

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

#### 来源

> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs)

## 解题思路

思路：二分+回溯剪枝

题目等价于：把n个数字划分成k组，对每一组数字求和后取最大的和，求最大和的最小值。如果直接暴力枚举的话，时间复杂度为$$O(k^n)$$，当$$n=k=12$$时候一定会超时。

考虑到要求的答案具有单调性，即：如果在最大工作时间为$$res$$时，存在一种分配方法，能让所有工人完成分配的工作，那么对于任意的$$i > res$$，也有一种分配方法能够让所有工人完成分配的工作。

因此我们可以对答案进行二分，然后利用回溯法对答案的可行性进行判断。

在回溯过程中，还可以进行一些优化：

1. 优先分配工作量大的任务。（直觉上来看，优先分配工作量大的任务，能够更快的找出不可行解；在搜索过程中，优先分配工作量少的工作会使工作量大的工作最后更可能无法被分配）；
2. 由于工人之间都是相同的（没有顺序），因此可以先定只有当前一个工人已被分配工作后，才为后面的工人分配工作；
3. 如果将某一工作分配给某一工人，改工人超过了最大工作时间，则不能为该工人分配工作。

另外，还有[状压dp](https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/wan-cheng-suo-you-gong-zuo-de-zui-duan-s-hrhu/)解法，留个坑。

## 代码

```cpp
class Solution {
public:
    // 把n个数字划分成k组，对每一组数字求和后取最大的和，求最大和的最小值。
    int sum[20];
    bool dfs(int dps, vector<int>& jobs, int n, int k, int mid){
        if(dps == n){  
            int maxSum = 0;
            for(int i = 0; i < k; i++){
                if(sum[i] > maxSum){
                    maxSum = sum[i];
                }
            }
            return maxSum <= mid;
        }
        for(int i = 0; i < k; i++){
            // 从第0个工人到第k-1个工人一次分配工作
            // 只有当前一个工人被分配工作后，才为后面的工人分配工作。
            if(i > 0 && sum[i-1] == 0) break;
            // 工作时间超过了mid，不能分配工作
            if(sum[i] + jobs[dps] > mid) continue;
            sum[i] += jobs[dps];
            if(dfs(dps+1, jobs, n, k, mid)){
                sum[i] -= jobs[dps];
                return true;
            }
            sum[i] -= jobs[dps];
        }
        return false;
    }
    int minimumTimeRequired(vector<int>& jobs, int k) {
        memset(sum, 0, sizeof(sum));
        const int n = jobs.size();
        // 优先分配时间长的工作
        sort(jobs.begin(), jobs.end(), greater<int>());
        int l = 1, r = 0;
        for(int& job: jobs){
            r += job;
        }
        while(l <= r){
            int mid = (r - l) / 2 + l;
            if(dfs(0, jobs, n, k, mid)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
};
```

## 用时和内存

> 执行用时：4 ms，在所有 C++提交中击败了95.88%的用户
> 内存消耗：7.2 MB，在所有 C++提交中击败了80.49%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.8】LeetCode每日一题·完成所有工作的最短时间

所有评论

暂无评论

新增评论