Find Minimum Time to Finish All Jobs
Hard · Dynamic Programming · Array · Dynamic Programming · Backtracking · Bit Manipulation · Bitmask
Problem
You are given jobs, where jobs[i] is how long job i takes, and k workers. Every job must go to exactly one worker, and a worker's working time is the sum of the times of its jobs.
Assign the jobs so that the largest working time is as small as possible, and return that largest working time.
Examples
Input: jobs = [5,3,4,2], k = 2 Output: 7
Give 5 and 2 to one worker and 3 and 4 to the other: both work 7. The total is 14, so no split can do better.
Input: jobs = [10,1,1], k = 3 Output: 10
Each worker takes one job. The job of length 10 alone takes 10, so that is the least possible.
Constraints
- 1 <= k <= len(jobs) <= 12
- 1 <= jobs[i] <= 10^7
Approaches
- Try every assignment — time O(k^n), space O(n + k)
Follow-up
Backtracking can also be made fast in practice: sort the jobs longest first, stop any branch whose largest load already reaches the best answer found, and never try two workers with the same current load for the same job. Binary searching the answer and asking "can it be done within T?" with that backtracking is another common route.
Related problems
Start free on Cariara · Coding problems · System design studio
