Find Minimum Time to Finish All Jobs: Backtracking with Pruning

You are given an integer array jobs, where jobs[i] is the time it takes to complete the i-th job. You also have k workers. Each job must be assigned to exactly one worker, and each worker can be assigned multiple jobs. Return the minimum possible value of the maximum working time of any worker.

This is LeetCode 1723: Find Minimum Time to Finish All Jobs, and it is a classic example of binary search on the answer combined with backtracking. The problem teaches you how to distribute work across workers optimally, a pattern that shows up in load balancing, task scheduling, and partition problems.

Why this problem matters

Many optimization problems ask you to minimize a maximum (or maximize a minimum). This "minimax" pattern appears in problems like splitting an array into k subarrays to minimize the largest sum, distributing candies, or scheduling machines. The trick is always the same: binary search on the answer, then check feasibility.

What makes LeetCode 1723 harder than most is the feasibility check. You cannot just greedily assign jobs to workers. The order matters, and you need backtracking to explore different assignments. Without careful pruning, the backtracking explodes. This problem forces you to learn three pruning techniques that apply broadly to any assignment or partition backtracking problem.

The key insight

Instead of searching over all possible assignments directly, you flip the question: "Can I finish all jobs if no worker exceeds a time limit of mid?" If you can answer this yes/no question efficiently, you can binary search on mid to find the smallest feasible limit.

The lower bound for binary search is max(jobs), because at minimum one worker must handle the largest job. The upper bound is sum(jobs), the case where a single worker does everything.

For the feasibility check, you assign jobs one by one (sorted largest first) to workers using backtracking. Three pruning rules make this fast:

1. Skip overflow: if assigning a job to a worker would exceed the limit, skip that worker.
2. Skip duplicates: if two workers have the same current load, assigning the job to either produces identical subtrees. Only try one.
3. Empty worker cutoff: if assigning a job to an empty worker fails, then assigning it to any other empty worker will also fail. Stop immediately.

The solution

def minimum_time_required(jobs: list[int], k: int) -> int:
    jobs.sort(reverse=True)
    lo, hi = jobs[0], sum(jobs)

    def can_assign(idx, workers, limit):
        if idx == len(jobs):
            return True
        seen = set()
        for i in range(len(workers)):
            if workers[i] + jobs[idx] > limit:
                continue
            if workers[i] in seen:
                continue
            seen.add(workers[i])
            workers[i] += jobs[idx]
            if can_assign(idx + 1, workers, limit):
                return True
            workers[i] -= jobs[idx]
            if workers[i] == 0:
                break
        return False

    while lo < hi:
        mid = (lo + hi) // 2
        if can_assign(0, [0] * k, mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

Let's walk through what each piece does.

The outer binary search narrows the answer range. For each candidate mid, we ask: "Can we distribute all jobs among k workers so that no worker exceeds mid total time?" If yes, we try a tighter bound. If no, we raise the lower bound.

The can_assign function is the backtracking core. It tries to place jobs[idx] into each worker one at a time. If placing the job does not exceed the limit, it recurses to place the next job. If the recursion succeeds, we found a valid assignment. If not, we undo the placement and try the next worker.

The seen set handles the duplicate-worker pruning. If two workers currently have the same load, assigning the current job to either one leads to the same set of future choices. We only try one to avoid redundant work.

The if workers[i] == 0: break line is the empty-worker cutoff. If we tried assigning a job to an empty worker and the recursion failed, then assigning the same job to a different empty worker will also fail (they are in the same state). We break out of the loop immediately.

Visual walkthrough

Let's trace through a small example with jobs = [3, 2, 3] and k = 3. The binary search narrows the answer from the range [3, 8] down to 3. Watch how the backtracking assigns jobs to workers and how pruning eliminates redundant branches.

Notice that sorting descending and the three pruning rules work together. Sorting forces large jobs to be placed first, which triggers overflows and empty-worker cutoffs earlier. The duplicate-worker check prevents exploring symmetric assignments. Together, these techniques reduce the effective search space from exponential to manageable.

Complexity analysis

Time is O(log(S) * k^n) in the worst case, where S is sum(jobs) and n is the number of jobs. The binary search runs O(log(S)) iterations. Each iteration runs the backtracking, which in the worst case tries k choices for each of n jobs. In practice, the pruning rules reduce this dramatically. The sort-descending plus empty-worker cutoff plus duplicate-skip typically bring runtime well within limits for the given constraints (n up to 12, k up to 12).

Space is O(n + k). The recursion depth is n (one level per job), and the workers array has k entries. The seen set at each level has at most k entries but is created fresh each call and freed on return.

The building blocks

1. Binary search on the answer

The pattern of binary searching on a minimax value and checking feasibility:

lo, hi = lower_bound, upper_bound
while lo < hi:
    mid = (lo + hi) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

This template works whenever you need to minimize the maximum of something. You binary search on what the answer could be, and for each candidate you run a feasibility check. The key is defining good bounds and writing an efficient feasibility function. You will see this exact pattern in "Split Array Largest Sum" (LeetCode 410), "Capacity to Ship Packages" (LeetCode 1011), and many other minimax problems.

2. Backtracking with symmetry pruning

The pattern of assigning items to buckets while skipping symmetric states:

def backtrack(idx, buckets, limit):
    if idx == len(items):
        return True
    seen = set()
    for i in range(len(buckets)):
        if buckets[i] + items[idx] > limit:
            continue
        if buckets[i] in seen:
            continue
        seen.add(buckets[i])
        buckets[i] += items[idx]
        if backtrack(idx + 1, buckets, limit):
            return True
        buckets[i] -= items[idx]
        if buckets[i] == 0:
            break
    return False

The duplicate-skip with a seen set and the empty-bucket break are the two critical optimizations. Without them, you explore many equivalent branches. This exact pattern applies to "Partition to K Equal Sum Subsets" (LeetCode 698), "Fair Distribution of Cookies" (LeetCode 2305), and any problem that asks you to split items into k groups optimally.

Edge cases

Before submitting, think through these scenarios:

• k equals the number of jobs: each worker gets exactly one job. The answer is max(jobs).
• k is 1: one worker does everything. The answer is sum(jobs).
• All jobs are equal: the answer is ceil(n / k) * jobs[0], because you spread them as evenly as possible.
• Single job: the answer is that job's time, regardless of k.
• k is larger than the number of jobs: some workers stay idle. The answer is still max(jobs).
• Jobs array has one large job and many small ones: the large job dominates. The answer is at least max(jobs), and you need to check if small jobs can be distributed without exceeding it.

From understanding to recall

You have seen how binary search on the answer combines with backtracking to solve this minimax assignment problem. The logic makes sense when you read it. But reproducing it under pressure is where people stumble.

The details that trip people up are the pruning rules. When do you check the seen set? When do you break on an empty worker? Do you sort ascending or descending? These are not conceptual misunderstandings. They are recall gaps, and they cost time in interviews.

Spaced repetition is how you close them. You practice writing the binary search template, the backtracking with the seen set and empty-bucket break, and the sort-descending setup from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "minimize the maximum" in a problem description, and the binary search plus backtracking template flows out without hesitation.

Related posts

• Combination Sum - Core backtracking pattern for exploring combinations with constraint checking
• N-Queens - Classic constraint-satisfaction backtracking with pruning to eliminate invalid placements
• Permutations - Foundational backtracking problem that teaches the assign-and-recurse pattern

CodeBricks breaks Find Minimum Time to Finish All Jobs into its binary search and backtracking-with-pruning building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a minimax assignment problem shows up in your interview, you do not think about it. You just write it.