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] <= 107In #1723 Find Minimum Time to Finish All Jobs, the goal is to distribute jobs among k workers so that the maximum working time of any worker is minimized. This makes the problem a classic search and partition challenge.
A common strategy is to combine binary search with backtracking. Binary search guesses the minimum possible maximum workload, while backtracking attempts to assign jobs to workers without exceeding that limit. Careful pruning—such as skipping identical worker states or stopping when a worker receives no job—greatly reduces the search space.
Another advanced technique uses bitmask dynamic programming. Each subset of jobs is represented by a bitmask, and precomputed workload sums allow efficient transitions when assigning subsets to workers.
Backtracking with pruning is typically the most practical solution for interview settings, offering manageable performance for the problem’s constraints. Bitmask DP provides an alternative perspective when exploring state compression techniques.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search + Backtracking | O(k * 2^n) in the worst case with pruning | O(n + k) |
| Bitmask Dynamic Programming | O(k * 3^n) | O(2^n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
We can select a subset of tasks and assign it to a worker then solve the subproblem on the remaining tasks
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bitmasking allows each subset of jobs to be represented as a binary number, making it easy to iterate through combinations of tasks. This technique is useful in DP solutions where subsets of jobs are assigned to workers.
Yes, variations of job scheduling and load balancing problems are frequently asked in top tech interviews. This problem tests backtracking optimization, pruning strategies, and understanding of bitmask dynamic programming.
Arrays are primarily used to track job durations and worker workloads. When using dynamic programming, bitmasks are helpful for representing subsets of jobs and enabling efficient state compression.
A common optimal strategy combines binary search with backtracking. Binary search determines the smallest possible maximum workload, while backtracking assigns jobs to workers under that limit with strong pruning to reduce unnecessary states.