LeetCode 1723 - Find Minimum Time to Finish All Jobs
This problem is asking us to assign a set of jobs, each with a specific time requirement, to k workers such that every job is assigned to exactly one worker, and we minimize the maximum total working time among all workers.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask
Solution
Problem Understanding
This problem is asking us to assign a set of jobs, each with a specific time requirement, to k workers such that every job is assigned to exactly one worker, and we minimize the maximum total working time among all workers. The input jobs is an integer array where jobs[i] represents the time needed to complete the i-th job. The integer k specifies the number of workers available. The output is a single integer representing the minimum possible value of the largest workload assigned to any worker.
The constraints provide important information: the number of jobs n is at most 12, and each job can take up to 10^7 units of time. The small value of n hints that exponential approaches (like backtracking with pruning) are feasible. Key edge cases include scenarios where k equals n (each worker can take exactly one job) or where k is 1 (all jobs must go to a single worker). The problem guarantees at least one worker and at least one job, so we do not need to handle empty inputs.
The challenge is that naive approaches of trying every possible assignment explode combinatorially. We need a strategy that efficiently explores the space of assignments while pruning infeasible or suboptimal solutions.
Approaches
The brute-force approach would attempt all possible distributions of jobs among workers. Since each job can go to any worker, there are k^n possible assignments. For each assignment, we would compute the maximum working time and keep track of the smallest maximum. While correct, this approach is infeasible even for n = 12 and k = 4, as it requires examining millions of possibilities.
The key insight for an optimal solution is that we can use backtracking with pruning combined with binary search on the answer. The maximum working time must lie between the largest single job time and the sum of all job times. We can perform a binary search on this range and, for each candidate maximum time, check whether it is possible to assign jobs to workers without exceeding this limit. The checking can be done via a recursive backtracking algorithm that attempts to assign jobs one by one, skipping assignments that would exceed the candidate limit. This reduces the search space dramatically.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(k^n) | O(n) | Tries all possible job assignments; infeasible for n > 10 |
| Backtracking + Binary Search | O(k * 2^n) | O(n) | Uses backtracking with pruning; binary search on answer range |
Algorithm Walkthrough
- Initialize search bounds: Set
lowto the maximum job time (since no worker can have less than the largest job) andhighto the sum of all jobs (all jobs assigned to one worker). - Binary search loop: While
low < high, computemid = (low + high) // 2. This represents a candidate maximum workload. - Check feasibility: Use a recursive function to try assigning each job to one of the
kworkers without exceedingmidworkload. If any worker exceedsmid, backtrack. - Prune effectively: Skip assigning a job to a worker if that worker already has the same workload as the previous worker tried at this recursion level (avoids symmetric states).
- Update bounds: If the candidate
midis feasible, reducehigh = mid; otherwise, increaselow = mid + 1. - Return result: Once the search ends,
low(orhigh) will hold the minimum possible maximum workload.
Why it works: The binary search ensures that we systematically narrow the range of possible maximum workloads. The backtracking ensures that we explore all valid job distributions for each candidate maximum. Pruning avoids redundant exploration, guaranteeing efficiency. The combination guarantees that the algorithm finds the minimum possible maximum workload.
Python Solution
from typing import List
class Solution:
def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
def can_assign(jobs, workloads, idx, limit):
if idx == len(jobs):
return True
current_job = jobs[idx]
for i in range(k):
if workloads[i] + current_job <= limit:
workloads[i] += current_job
if can_assign(jobs, workloads, idx + 1, limit):
return True
workloads[i] -= current_job
# Prune identical states to reduce redundant recursion
if workloads[i] == 0:
break
return False
jobs.sort(reverse=True)
low, high = max(jobs), sum(jobs)
while low < high:
mid = (low + high) // 2
if can_assign(jobs, [0] * k, 0, mid):
high = mid
else:
low = mid + 1
return low
Implementation walkthrough: We first sort jobs in descending order to assign larger jobs first, which often triggers pruning earlier. The helper can_assign recursively tries to allocate jobs to workers without exceeding the current candidate limit. The pruning condition if workloads[i] == 0: break avoids exploring symmetric states where jobs are assigned to identical empty workers. The binary search iteratively narrows down the feasible maximum workload.
Go Solution
func minimumTimeRequired(jobs []int, k int) int {
var canAssign func(jobs []int, workloads []int, idx int, limit int) bool
canAssign = func(jobs []int, workloads []int, idx int, limit int) bool {
if idx == len(jobs) {
return true
}
job := jobs[idx]
for i := 0; i < k; i++ {
if workloads[i]+job <= limit {
workloads[i] += job
if canAssign(jobs, workloads, idx+1, limit) {
return true
}
workloads[i] -= job
}
if workloads[i] == 0 {
break
}
}
return false
}
sort.Slice(jobs, func(i, j int) bool { return jobs[i] > jobs[j] })
low, high := 0, 0
for _, job := range jobs {
if job > low {
low = job
}
high += job
}
for low < high {
mid := (low + high) / 2
workloads := make([]int, k)
if canAssign(jobs, workloads, 0, mid) {
high = mid
} else {
low = mid + 1
}
}
return low
}
Go-specific notes: We use slices for workloads and jobs. Sorting uses sort.Slice. Recursive functions are defined using a variable canAssign with a closure for recursion. No need for type hints as in Python. Slices are automatically initialized with zeros, similar to Python lists.
Worked Examples
Example 1: jobs = [3,2,3], k = 3
| Step | Jobs Remaining | Worker Workloads | Action |
|---|---|---|---|
| Start | [3,2,3] | [0,0,0] | Assign largest job 3 to worker 0 |
| Recursion | [2,3] | [3,0,0] | Assign 2 to worker 1 |
| Recursion | [3] | [3,2,0] | Assign 3 to worker 2 |
| Done | [] | [3,2,3] | Maximum workload 3, feasible |
Example 2: jobs = [1,2,4,7,8], k = 2
Binary search will test candidate max workloads. At mid=11, backtracking can assign: Worker1: 1+2+8=11, Worker2: 4+7=11. Feasible, so search narrows to 11. No lower value is feasible. Minimum max workload is 11.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(k * 2^n) | Each subset of jobs may be explored; pruning reduces practical time |
| Space | O(n) | Recursion stack depth up to n; workloads array uses O(k) |
Even though worst-case time seems exponential, pruning and sorting large jobs first significantly reduce the number of recursive calls.
Test Cases
# Provided examples
assert Solution().minimumTimeRequired([3,2,3], 3) == 3 # each job to one worker
assert Solution().minimumTimeRequired([1,2,4,7,8], 2) == 11 # optimal distribution
# Edge cases
assert Solution().minimumTimeRequired([5], 1) == 5 # single job single worker
assert Solution().minimumTimeRequired([5,5,5,5], 4) == 5 # jobs equal workers
assert Solution().minimumTimeRequired([1,2,3,4], 1) == 10 # all jobs to one worker
assert Solution().minimumTimeRequired([1,1,1,1,1], 2) == 3 # distribute evenly
# Stress cases
assert Solution().minimumTimeRequired([i for i in range(1,13)], 4) == 15 # sum partition