Question

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

English Version

题目描述

给你两个 下标从 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

解法

方法一

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
}