Find Minimum Time to Finish All Jobs - Video Solutions

Problem 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.