2323. Find Minimum Time to Finish All Jobs II

MediumGreedyArraySorting
Leetcode Link

Problem Description

You are provided with two integer arrays, jobs and workers, each indexed starting from 0. The arrays have the same lengths, meaning they contain an equal number of elements. jobs[i] represents the time required to complete the i-th job, while workers[j] represents the time a j-th worker can dedicate to working each day. The task is to assign each job to one worker so that every worker gets exactly one job. Your goal is to calculate the minimum number of days necessary to finish all the jobs after they have been allocated to the workers.

Intuition

The intuition behind the solution involves two observations:

  1. Sorting Pattern: If we sort both the jobs and workers arrays in ascending order, we ensure the biggest jobs are matched with the workers who can work the most per day. This helps us in minimizing the overall time since we are using the maximum capacity of the most efficient workers.

  2. Minimum Days Calculation: After sorting, we pair each job with a worker. To calculate the number of days a worker needs to complete a job, we can take the time needed for the job (a) and divide it by the time the worker can put in each day (b). Since we are dealing with whole days, we need to round up, which is achieved by (a + b - 1) // b in Python (integer division with ceiling).

The max function applied to the result of these calculations across all job-worker pairs ensures that we find the scenario that takes the longest. This is the minimum number of days needed to complete all jobs, since all jobs are being worked on simultaneously, and once the job taking the longest is done, all other jobs would have also been completed.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these pictures shows the visit order of a depth-first search?

Solution Approach

The solution uses a greedy algorithm approach which is implemented through sorting and pairing, leading to an efficient way to calculate the minimum time necessary to complete all jobs. Here's a walkthrough of the implementation:

  • Firstly, we sort both the jobs and workers arrays in ascending order. By doing this, we can pair the largest job with the worker who can work the longest hours, and so on down the line. Sorting is a common algorithmic pattern for problems related to optimization, as it often helps to align data in a way that simplifies pairing or comparison.

  • We then iterate over the pairs of sorted jobs and workers. These pairs are generated by zipping the two arrays together using Python's built-in zip() function, which pairs elements with the same index from each of the input sequences.

  • For each pair (a, b) taken from zip(jobs, workers), we calculate the number of days it would take for worker b to complete job a. This is where the formula (a + b - 1) // b comes into play. It ensures that we perform the integer division with a ceiling effect since we are dealing with full days. If a job doesn't require a full extra day, we still count the partial day as a full one, since a worker cannot be partially assigned to a job each day.

  • The max() function is then used on the sequence of these calculations. Because each worker is working on different jobs in parallel, the overall completion time for all jobs is dictated by the job-worker pair that takes the longest. This longest time will be the maximum value out of the individual times calculated.

In summary, by sorting the jobs and workers, we facilitate an optimal pairing strategy. Then we calculate the time each optimal job-worker pair takes, ensuring to account for partial days as full. Lastly, we identify the longest duration out of these pairs as our solution.

Data Structures used:

  • Arrays: to store the input jobs and workers data and manipulate it through sorting.
  • Integers: to represent individual job times and worker capacities, and to calculate and represent the minimum number of days required.

Patterns used:

  • Sorting: to optimally align the jobs to workers.
  • Greedy: to pair the highest capacity workers with the largest jobs to minimize overall time.
  • Iteration: to go through the pairs of jobs and workers and calculate the time taken for each.
  • Calculation: to determine the number of days for each pair and identify the maximum completion time.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the following arrays for jobs and workers:

1jobs = [3, 2, 7]
2workers = [1, 5, 3]

Here's how we implement our solution:

  1. First, we sort both arrays to align the largest jobs with the workers who can dedicate the most time per day. After sorting:

    1jobs = [2, 3, 7]
2workers = [1, 3, 5]

  2. Next, we pair each job with a worker by zipping the two sorted arrays.

    1paired = zip([2, 3, 7], [1, 3, 5])
2paired = [(2, 1), (3, 3), (7, 5)]

  3. Now, for each paired tuple, calculate the number of days it takes for the worker to finish the job using (a + b - 1) // b. Here, a is the time needed for the job, and b is the time the worker can work per day.

    • For the first pair (2, 1), the calculation is (2 + 1 - 1) // 1 = 2 days.
    • For the second pair (3, 3), the calculation is (3 + 3 - 1) // 3 = 1 day.
    • For the third pair (7, 5), the calculation is (7 + 5 - 1) // 5 = 2 days.

  4. Last, we find the maximum number of days from all the pairs; this will be the minimum number of days required to complete all the jobs.

    1max_days = max([2, 1, 2]) = 2

So, with the given job and worker assignments, the minimum number of days required to finish all the jobs is 2 days.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:
5        # Sort the lists to ensure that the shortest jobs are matched with
6        # the workers who take the least amount of time per unit.
7        jobs.sort()
8        workers.sort()
9
10        # Calculate the time taken for each worker to complete their job.
11        # We're using (job_duration + worker_speed - 1) // worker_speed to 
12        # determine the minimum number of full time units needed for completion.
13        # The -1 is used to ensure that we do not add an extra unnecessary 
14        # time unit if job_duration is perfectly divisible by worker_speed.
15        # For each pair of job and worker, the time required for that worker 
16        # to complete their job is calculated.
17        times = [(job_duration + worker_speed - 1) // worker_speed for job_duration, worker_speed in zip(jobs, workers)]
18
19        # The maximum time among all the workers is what will determine
20        # the total time required to finish all jobs, since we have to wait for
21        # the slowest job-worker pair to finish.
22        return max(times)
23
1import java.util.Arrays; // Necessary import for Arrays.sort()
2
3class Solution {
4  
5    // Method to calculate the minimum time needed to assign jobs to workers such that each worker gets exactly one job.
6    public int minimumTime(int[] jobs, int[] workers) {
7        Arrays.sort(jobs); // Sort the array of jobs in non-decreasing order.
8        Arrays.sort(workers); // Sort the array of workers in non-decreasing order.
9
10        int maximumTime = 0; // Initialize maximum time to 0.
11
12        for (int i = 0; i < jobs.length; ++i) {
13            // Calculate the time it takes for worker i to complete job i.
14            // Divide the job[i] work units by the workers[i] efficiency, rounding up to the nearest whole number.
15            int currentTime = (jobs[i] + workers[i] - 1) / workers[i];
16          
17            // Update maximumTime to be the maximum of itself and the time calculated for the current worker.
18            maximumTime = Math.max(maximumTime, currentTime);
19        }
20
21        // Return the overall maximum time it takes for all jobs to be completed.
22        return maximumTime;
23    }
24}
25
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    // This function calculates the minimum time required to assign jobs to workers
8    // such that each job is assigned to one worker, and the time taken is minimized.
9    // The time taken for each job-worker pair is the ceil of division of job by worker.
10    int minimumTime(vector<int>& jobs, vector<int>& workers) {
11        // Sort the jobs and workers vectors to match the smallest job with the fastest worker.
12        sort(jobs.begin(), jobs.end());
13        sort(workers.begin(), workers.end());
14      
15        int minimumTimeRequired = 0; // Initialize the minimum time required as 0.
16      
17        // Iterate over the matched pairs of jobs and workers.
18        for (int i = 0; i < jobs.size(); ++i) {
19            // Calculate the time taken for each job-worker pair, which is jobs[i] divided by workers[i],
20            // rounded up to the nearest integer, and update minimumTimeRequired if this time is larger.
21            minimumTimeRequired = max(minimumTimeRequired, (jobs[i] + workers[i] - 1) / workers[i]);
22        }
23      
24        // Return the maximum time out of all job-worker pairs as that would be the bottleneck.
25        return minimumTimeRequired;
26    }
27};
28
1// Import the necessary functions from lodash for sorting and max operations
2import { sortBy, max } from 'lodash';
3
4// This function calculates the minimum time required to assign jobs to workers
5// such that each job is assigned to one worker, and the time taken is minimized.
6// The time taken for each job-worker pair is the ceil of the division of the job by the worker.
7function minimumTime(jobs: number[], workers: number[]): number {
8    // Sort the jobs and workers arrays to match the smallest job with the fastest worker.
9    jobs = sortBy(jobs);
10    workers = sortBy(workers);
11  
12    let minimumTimeRequired = 0; // Initialize the minimum time required as 0.
13  
14    // Iterate over the matched pairs of jobs and workers.
15    for (let i = 0; i < jobs.length; ++i) {
16        // Calculate the time taken for each job-worker pair, which is jobs[i] divided by workers[i],
17        // rounded up to the nearest integer, by adding workers[i] - 1 before the division.
18        // Update minimumTimeRequired if this time is larger.
19        minimumTimeRequired = max([minimumTimeRequired, Math.ceil(jobs[i] / workers[i])]);
20    }
21  
22    // Return the maximum time out of all job-worker pairs as that would be the bottleneck.
23    return minimumTimeRequired;
24}
25
26// Usage example (if you want to test the function):
27// const jobsExample = [3, 2, 10];
28// const workersExample = [1, 2, 3];
29// const minTime = minimumTime(jobsExample, workersExample);
30// console.log(minTime); // Output will be the minimum time required based on the job and worker assignments.
31
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into the following parts:

  1. Sorting the jobs list: Sorting an array of n items has a time complexity of O(n log n).
  2. Sorting the workers list: This is another sorting operation also with O(n log n), assuming workers list has the same length as jobs.

Since these are two consecutive operations, the combined time complexity for both sorts will still be O(n log n) because the constants are dropped in Big O notation.

  1. The zip function and the comprehension: Creating pairs of jobs and workers with zip is O(n) and the comprehension iterates over each pair once, making it O(n) as well.

Combining all the above, we see that the most time-consuming operations are the sorts. Therefore, the overall time complexity of the code is O(n log n).

Space Complexity

For space complexity:

  1. Sorting the lists in-place: Since Python's sort method on lists sorts the list in place, it doesn't use extra space proportional to the input size. Therefore, the space complexity for the sort operation is O(1).

  2. zip and the comprehension: zip takes O(1) additional space as it returns an iterator, and the comprehension also takes O(1) space because it only computes the maximum time without storing intermediate results in an array or list.

Hence, the total space complexity of the code is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫