2323. Find Minimum Time to Finish All Jobs II
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:
-
Sorting Pattern: If we sort both the
jobs
andworkers
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. -
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.
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
andworkers
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
andworkers
. These pairs are generated by zipping the two arrays together using Python's built-inzip()
function, which pairs elements with the same index from each of the input sequences. -
For each pair
(a, b)
taken fromzip(jobs, workers)
, we calculate the number of days it would take for workerb
to complete joba
. 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
andworkers
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following arrays for jobs and workers:
jobs = [3, 2, 7] workers = [1, 5, 3]
Here's how we implement our solution:
-
First, we sort both arrays to align the largest jobs with the workers who can dedicate the most time per day. After sorting:
jobs = [2, 3, 7] workers = [1, 3, 5]
-
Next, we pair each job with a worker by zipping the two sorted arrays.
paired = zip([2, 3, 7], [1, 3, 5]) paired = [(2, 1), (3, 3), (7, 5)]
-
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, andb
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
.
- For the first pair
-
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.
max_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
Time and Space Complexity
Time Complexity
The time complexity of the given code can be broken down into the following parts:
- Sorting the
jobs
list: Sorting an array ofn
items has a time complexity ofO(n log n)
. - Sorting the
workers
list: This is another sorting operation also withO(n log n)
, assumingworkers
list has the same length asjobs
.
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.
- The
zip
function and the comprehension: Creating pairs of jobs and workers withzip
isO(n)
and the comprehension iterates over each pair once, making itO(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:
-
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)
. -
zip
and the comprehension:zip
takesO(1)
additional space as it returns an iterator, and the comprehension also takesO(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.
Which of the following is a good use case for backtracking?
Recommended Readings
Greedy Introduction div class responsive iframe iframe 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 div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!