Find Minimum Time to Finish All Jobs II - Solution & Explanation
Problem Statement
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 the minimum number of days needed to complete all the jobs after assignment.
Example 1:
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:
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.length1 <= n <= 1051 <= jobs[i], workers[i] <= 105
Approach Overview
Problem Overview: You are given two arrays: jobs where jobs[i] represents the amount of work required for a job, and workers where workers[i] represents how much work a worker can complete per unit time. Each worker must take exactly one job. The goal is to assign jobs so the time when the last job finishes is minimized.
Approach 1: Brute Force Assignment (O(n!))
The direct idea is to try every possible assignment of workers to jobs and compute the finishing time for each configuration. For a pair (job, worker), the time required is ceil(job / worker). For each permutation, compute the maximum time across all pairs and keep the minimum across permutations. This guarantees the optimal assignment but quickly becomes infeasible since the number of permutations is n!. Space complexity is O(n) for recursion or permutation tracking. This approach only works for very small inputs and mainly demonstrates the assignment search space.
Approach 2: Binary Search on Time + Greedy Check (O(n log n + n log T))
Another idea is to guess the minimum finishing time using binary search. For a candidate time T, a worker can complete a job if worker[i] * T ≥ job[j]. Sort both arrays and greedily match workers to jobs while verifying whether all jobs can be finished within T. If feasible, try a smaller time; otherwise increase the bound. The sorting step dominates initially, while each feasibility check scans the arrays. Space complexity remains O(1) beyond sorting. This approach works but adds unnecessary complexity compared to the direct greedy observation.
Approach 3: Greedy Sorting (O(n log n))
The key insight: to minimize the maximum completion time, pair the largest job with the strongest worker. If a large job is assigned to a weak worker, the required time increases dramatically. Sorting both arrays ensures balanced assignments where stronger workers handle heavier jobs. After sorting, iterate once and compute time = ceil(jobs[i] / workers[i]) for each pair, tracking the maximum value. That maximum represents the time when the last job finishes. Sorting dominates the runtime with O(n log n) time and O(1) extra space (ignoring sort stack). This greedy pairing works because any swap that assigns a larger job to a weaker worker only increases the maximum completion time.
Relevant concepts include array manipulation, greedy decision making, and sorting strategies for optimal pairing.
Recommended for interviews: The greedy sorting approach is the expected solution. It shows you recognize the pairing strategy that minimizes the worst-case ratio. Mentioning the brute force assignment shows you understand the search space, but implementing the O(n log n) greedy solution demonstrates strong algorithmic reasoning.
Solution
To minimize the number of days required to complete all jobs, we can try to assign longer jobs to workers who can work longer hours.
Therefore, we can first sort jobs and workers, then assign jobs to workers based on their indices. Finally, we calculate the maximum ratio of job time to worker time.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the number of jobs.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Job Assignment | O(n!) | O(n) | Conceptual baseline to understand all possible assignments |
| Binary Search + Greedy Feasibility Check | O(n log n + n log T) | O(1) | Useful when the answer space can be searched via time limits |
| Greedy Sorting (Optimal) | O(n log n) | O(1) | General case; pair largest jobs with strongest workers |
Video Solution
Leetcode 2323. Find Minimum Time to Finish All Jobs II - greedy • Code-Yao • 748 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Find Minimum Time to Finish All Jobs II easy or hard?
Find Minimum Time to Finish All Jobs II Python/Java solution
How to solve Find Minimum Time to Finish All Jobs II in O(n log n)?
What is the best approach for Find Minimum Time to Finish All Jobs II?
Is Find Minimum Time to Finish All Jobs II asked at Google/Amazon/Meta?
What data structure is used in Find Minimum Time to Finish All Jobs II?
What is the time complexity of Find Minimum Time to Finish All Jobs II?
Ready to solve this problem?
Practice Find Minimum Time to Finish All Jobs II with our built-in code editor and test cases.
Practice on FleetCode