Skip to main content
Talentd

Find Minimum Time to Finish All Jobs - Solution & Explanation

HardArrayDynamic ProgrammingBacktrackingBit Manipulation11 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 <= 12
  • 1 <= jobs[i] <= 107

Approach Overview

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.

Approach 1: Backtracking with Pruning

This approach uses backtracking to explore all possible assignments of jobs to workers. The key idea is to use pruning to eliminate suboptimal assignments early. We start by sorting jobs in descending order, as this often leads to earlier pruning due to higher jobs being assigned first.

We keep track of each worker's current workload and attempt to assign each job to every worker, recursively minimizing the maximum workload across workers. Pruning is applied if, at any point, the current workload exceeds the best solution found.

The code defines a recursive function, dfs, that attempts to assign each job to one of the workers, updating their workload. We check if the current workloads exceed the best found so far and prune branches that cannot improve the current best solution. Moreover, we skip further allocations to a worker if it's currently at zero load to avoid redundant computations, leveraging symmetrical permutations.

Code

PythonJavaC

Python

Java

C

Complexity

Time Complexity: O(k^n), where n is the number of jobs and k is the number of workers due to factorial growth of permutations.

Space Complexity: O(n), as depth of recursion is at most the number of jobs.

Try this approach in the editor →

Approach 2: Binary Search with Feasibility Check

Binary search efficiently finds the minimal possible maximum workload by guessing a mid value and checking its feasibility using a greedy strategy – checking if it's possible to partition jobs into k or fewer subsets without exceeding this mid value.

Each check involves trying to assign jobs to workers while ensuring no worker exceeds the guess workload. If feasible, we search the lower half; otherwise, the upper half. This balances finding the global optimum workload under constraints.

This code defines a nested function canFinish, which uses recursive backtracking to determine if the jobs can be completed within a specified load per worker. Outer code uses binary search on potential workloads, moving left if possible and extending right otherwise. Sorting jobs helps earlier feasibility checks succeed.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n*k*log(sum(jobs))) due to binary search within potential max load and recursive checks.

Space Complexity: O(k + n) for workload tracking and recursion depth.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Pruning

Time Complexity: O(k^n), where n is the number of jobs and k is the number of workers due to factorial growth of permutations.

Space Complexity: O(n), as depth of recursion is at most the number of jobs.

Binary Search with Feasibility Check

Time Complexity: O(n*k*log(sum(jobs))) due to binary search within potential max load and recursive checks.

Space Complexity: O(k + n) for workload tracking and recursion depth.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with PruningO(k^n) worst caseO(k + n)Best when n is small (≤12) and strong pruning can eliminate most branches
Binary Search + Feasibility DFSO(log S * k^n)O(k + n)Preferred when reasoning about minimizing maximum load; binary search reduces the answer space

Video Solution

LeetCode 1723. Find Minimum Time to Finish All Jobs • Happy Coding • 10,348 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Minimum Time to Finish All Jobs easy or hard?
This problem is classified as Hard because it combines combinatorial search with optimization. Efficient solutions require pruning strategies, careful state management, and sometimes binary search over the answer space.
Find Minimum Time to Finish All Jobs Python/Java solution
Typical implementations use DFS backtracking with pruning. Maintain a workloads array of size k and recursively assign jobs while tracking the current maximum load. The same logic works in Python, Java, and C++ with minor syntax differences.
How to solve Find Minimum Time to Finish All Jobs in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of job assignments. The optimal strategies use backtracking with pruning or binary search combined with DFS feasibility checks. These approaches significantly reduce the exponential search space but still have exponential worst‑case behavior.
What is the best approach for Find Minimum Time to Finish All Jobs?
Backtracking with pruning is the most widely used approach. It assigns jobs to workers recursively while pruning branches where the workload already exceeds the current best answer. With symmetry pruning and job sorting, the exponential search space becomes manageable for n up to around 12.
Is Find Minimum Time to Finish All Jobs asked at Google/Amazon/Meta?
Problems involving job scheduling, workload balancing, and minimizing maximum load appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test backtracking, pruning strategies, and optimization techniques such as binary search on the answer.
What data structure is used in Find Minimum Time to Finish All Jobs?
The core data structure is an array that tracks the current workload of each worker. During recursion or feasibility checks, this array is updated as jobs are assigned. Some variations also use bitmasks to represent subsets of jobs, linking the problem to bit manipulation and dynamic programming techniques.
What is the time complexity of Find Minimum Time to Finish All Jobs?
The worst‑case time complexity is O(k^n) because each of the n jobs can be assigned to any of the k workers. Practical implementations run much faster due to pruning and sorting optimizations. Space complexity is O(k + n) for recursion and worker workload tracking.

Ready to solve this problem?

Practice Find Minimum Time to Finish All Jobs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Minimum Time to Finish All Jobs II

Next

Minimum Number of Work Sessions to Finish the Tasks