2323. 完成所有工作的最短时间 II 🔒

题目描述

给你两个 下标从 0 开始 的整数数组 jobs 和 相等 长度的 workers ，其中 jobs[i]是完成第 i 个工作所需的时间，workers[j] 是第 j 个工人每天可以工作的时间。

每项工作都应该 正好 分配给一个工人，这样每个工人就 只能 完成一项工作。

返回分配后完成所有作业所需的最少天数。

 

示例 1:

输入: jobs = [5,2,4], workers = [1,7,5]
输出: 2
解释:
- 把第 2 个工人分配到第 0 个工作。他们花了 1 天时间完成这项工作。
- 把第 0 个工人分配到第 1 个工作。他们花了 2 天时间完成这项工作。
- 把第 1 个工人分配到第 2 个工作。他们花了 1 天时间完成这项工作。
所有工作完成需要 2 天，因此返回 2。
可以证明 2 天是最少需要的天数。

示例 2:

输入: jobs = [3,18,15,9], workers = [6,5,1,3]
输出: 3
解释:
- 把第 2 个工人分配到第 0 个工作。他花了 3 天时间完成这项工作。
- 把第 0 个工人分配到第 1 个工作。他花了 3 天时间完成这项工作。
- 把第 1 个工人分配到第 2 个工作。他花了 3 天时间完成这项工作。
- 把第 3 个工人分配到第 3 个工作。他花了 3 天时间完成这项工作。
完成所有工作需要 3 天，因此返回 3。
可以证明，3 天是最少需要的天数。

 

提示:

• n == jobs.length == workers.length
• 1 <= n <= 105
• 1 <= jobs[i], workers[i] <= 105

解法

方法一

Python3JavaC++Go

class Solution:
    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:
        jobs.sort()
        workers.sort()
        return max((a + b - 1) // b for a, b in zip(jobs, workers))

class Solution {
    public int minimumTime(int[] jobs, int[] workers) {
        Arrays.sort(jobs);
        Arrays.sort(workers);
        int ans = 0;
        for (int i = 0; i < jobs.length; ++i) {
            ans = Math.max(ans, (jobs[i] + workers[i] - 1) / workers[i]);
        }
        return ans;
    }
}

class Solution {
public:
    int minimumTime(vector<int>& jobs, vector<int>& workers) {
        sort(jobs.begin(), jobs.end());
        sort(workers.begin(), workers.end());
        int ans = 0;
        for (int i = 0; i < jobs.size(); ++i) ans = max(ans, (jobs[i] + workers[i] - 1) / workers[i]);
        return ans;
    }
};

func minimumTime(jobs []int, workers []int) int {
    sort.Ints(jobs)
    sort.Ints(workers)
    ans := 0
    for i, a := range jobs {
        b := workers[i]
        ans = max(ans, (a+b-1)/b)
    }
    return ans
}

评论