Problem

You are given two 0-indexed integer arrays jobs and workers of equal length, where jobs[i] is the amount of time needed to complete the ith job, and workers[j] is the amount of time the jth worker can work each day.

Each job should be assigned to exactly one worker, such that each worker completes exactly one job.

Return theminimum number of days needed to complete all the jobs after assignment.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: jobs = [5,2,4], workers = [1,7,5]
Output: 2
Explanation:
- Assign the 2nd worker to the 0th job. It takes them 1 day to finish the job.
- Assign the 0th worker to the 1st job. It takes them 2 days to finish the job.
- Assign the 1st worker to the 2nd job. It takes them 1 day to finish the job.
It takes 2 days for all the jobs to be completed, so return 2.
It can be proven that 2 days is the minimum number of days needed.

Example 2:

1
2
3
4
5
6
7
8
9

Input: jobs = [3,18,15,9], workers = [6,5,1,3]
Output: 3
Explanation:
- Assign the 2nd worker to the 0th job. It takes them 3 days to finish the job.
- Assign the 0th worker to the 1st job. It takes them 3 days to finish the job.
- Assign the 1st worker to the 2nd job. It takes them 3 days to finish the job.
- Assign the 3rd worker to the 3rd job. It takes them 3 days to finish the job.
It takes 3 days for all the jobs to be completed, so return 3.
It can be proven that 3 days is the minimum number of days needed.

Constraints:

  • n == jobs.length == workers.length
  • 1 <= n <= 10^5
  • 1 <= jobs[i], workers[i] <= 10^5

Solution

Method 1 – Greedy Assignment with Sorting

Intuition

To minimize the number of days, assign the hardest jobs to the most capable workers. By sorting both arrays and pairing the largest job with the largest worker, we ensure the minimum possible maximum days required.

Approach

  1. Sort jobs in ascending order.
  2. Sort workers in ascending order.
  3. For each pair (job, worker), compute the days needed as ceil(job / worker).
  4. The answer is the maximum days among all pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minimumTime(jobs []int, workers []int) int {
    sort.Ints(jobs)
    sort.Ints(workers)
    ans := 0
    for i := range jobs {
        d := (jobs[i] + workers[i] - 1) / workers[i]
        if d > ans { ans = d }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minimumTime(jobs: IntArray, workers: IntArray): Int {
        jobs.sort()
        workers.sort()
        var ans = 0
        for (i in jobs.indices) {
            ans = maxOf(ans, (jobs[i] + workers[i] - 1) / workers[i])
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minimumTime(self, jobs: list[int], workers: list[int]) -> int:
        jobs.sort()
        workers.sort()
        ans = 0
        for j, w in zip(jobs, workers):
            ans = max(ans, (j + w - 1) // w)
        return ans
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn minimum_time(mut jobs: Vec<i32>, mut workers: Vec<i32>) -> i32 {
        jobs.sort();
        workers.sort();
        jobs.iter().zip(workers.iter())
            .map(|(&j, &w)| (j + w - 1) / w)
            .max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    minimumTime(jobs: number[], workers: number[]): number {
        jobs.sort((a, b) => a - b);
        workers.sort((a, b) => a - b);
        let ans = 0;
        for (let i = 0; i < jobs.length; i++) {
            ans = Math.max(ans, Math.floor((jobs[i] + workers[i] - 1) / workers[i]));
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of jobs/workers. Sorting dominates.
  • 🧺 Space complexity: O(1), ignoring the space for sorting