You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the ith job.
There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.
Return the minimum possible maximum working time of any assignment.
Example 1:
Input: jobs = [3,2,3], k = 3 Output: 3 Explanation: By assigning each person one job, the maximum time is 3.
Example 2:
Input: jobs = [1,2,4,7,8], k = 2 Output: 11 Explanation: Assign the jobs the following way: Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11) Worker 2: 4, 7 (working time = 4 + 7 = 11) The maximum working time is 11.
Constraints:
1 <= k <= jobs.length <= 121 <= jobs[i] <= 107Problem Overview: You receive an array jobs where each value represents the time required for a job, and k workers. Assign every job to exactly one worker so that the maximum time any worker spends is minimized. The result is the smallest possible maximum workload across all workers.
Approach 1: Backtracking with Pruning (Time: O(k^n) worst case, Space: O(k + n))
This approach treats the problem as a search over all possible assignments of jobs to workers. Maintain an array representing the current workload of each worker. During recursion, assign the next job to each worker and track the maximum workload produced by that assignment. The key optimization is pruning: if the current assignment already produces a workload greater than the best answer found so far, stop exploring that branch. Additional pruning removes symmetric states, such as assigning a job to multiple workers with identical workloads. Because n ≤ 12 in typical constraints, aggressive pruning makes the search feasible. This technique is a classic application of backtracking combined with branch-and-bound optimization.
Approach 2: Binary Search with Feasibility Check (Time: O(log S * k^n) worst case, Space: O(k + n))
Instead of directly minimizing the maximum workload, binary search the answer. The lower bound is max(jobs) and the upper bound is sum(jobs). For each candidate limit, run a feasibility check: attempt to assign jobs so that no worker exceeds that limit. The feasibility check typically uses DFS/backtracking to distribute jobs while ensuring each worker's load stays ≤ limit. If assignment succeeds, the limit is feasible and the binary search moves left; otherwise move right. Sorting jobs in descending order dramatically reduces the search space because large jobs get placed first. This strategy combines greedy pruning with backtracking and is often easier to reason about during interviews.
Some advanced discussions also model subsets of jobs using bitmasks and memoization, linking the problem to bit manipulation and dynamic programming. However, the two approaches above are the most common practical solutions.
Recommended for interviews: Backtracking with pruning is the most common expected solution. It demonstrates understanding of state exploration and optimization techniques like symmetry pruning. The binary search + feasibility approach shows stronger algorithmic insight because it converts an optimization problem into a decision problem and reduces the search space using bounds.
This approach uses backtracking to explore all possible assignments of jobs to workers. The key idea is to use pruning to eliminate suboptimal assignments early. We start by sorting jobs in descending order, as this often leads to earlier pruning due to higher jobs being assigned first.
We keep track of each worker's current workload and attempt to assign each job to every worker, recursively minimizing the maximum workload across workers. Pruning is applied if, at any point, the current workload exceeds the best solution found.
The code defines a recursive function, dfs, that attempts to assign each job to one of the workers, updating their workload. We check if the current workloads exceed the best found so far and prune branches that cannot improve the current best solution. Moreover, we skip further allocations to a worker if it's currently at zero load to avoid redundant computations, leveraging symmetrical permutations.
Time Complexity: O(k^n), where n is the number of jobs and k is the number of workers due to factorial growth of permutations.
Space Complexity: O(n), as depth of recursion is at most the number of jobs.
Binary search efficiently finds the minimal possible maximum workload by guessing a mid value and checking its feasibility using a greedy strategy – checking if it's possible to partition jobs into k or fewer subsets without exceeding this mid value.
Each check involves trying to assign jobs to workers while ensuring no worker exceeds the guess workload. If feasible, we search the lower half; otherwise, the upper half. This balances finding the global optimum workload under constraints.
This code defines a nested function canFinish, which uses recursive backtracking to determine if the jobs can be completed within a specified load per worker. Outer code uses binary search on potential workloads, moving left if possible and extending right otherwise. Sorting jobs helps earlier feasibility checks succeed.
Time Complexity: O(n*k*log(sum(jobs))) due to binary search within potential max load and recursive checks.
Space Complexity: O(k + n) for workload tracking and recursion depth.
| Approach | Complexity |
|---|---|
| Backtracking with Pruning | Time Complexity: O(k^n), where n is the number of jobs and k is the number of workers due to factorial growth of permutations. Space Complexity: O(n), as depth of recursion is at most the number of jobs. |
| Binary Search with Feasibility Check | Time Complexity: O(n*k*log(sum(jobs))) due to binary search within potential max load and recursive checks. Space Complexity: O(k + n) for workload tracking and recursion depth. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(k^n) worst case | O(k + n) | Best when n is small (≤12) and strong pruning can eliminate most branches |
| Binary Search + Feasibility DFS | O(log S * k^n) | O(k + n) | Preferred when reasoning about minimizing maximum load; binary search reduces the answer space |
LeetCode 1723. Find Minimum Time to Finish All Jobs • Happy Coding • 10,082 views views
Watch 9 more video solutions →Practice Find Minimum Time to Finish All Jobs with our built-in code editor and test cases.
Practice on FleetCode