1723. Find Minimum Time to Finish All Jobs - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th 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] <= 10⁷

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.

Python

def minimumTimeRequired(jobs, k):
    jobs.sort(reverse=True)
    workloads = [0] * k
    best = [float('inf')]

    def dfs(i):
        if i == len(jobs):
            best[0] = min(best[0], max(workloads))
            return
        for j in range(k):
            workloads[j] += jobs[i]
            if workloads[j] < best[0]:
                dfs(i + 1)
            workloads[j] -= jobs[i]
            if workloads[j] == 0:
                break

    dfs(0)
    return best[0]

Java

class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int[] workloads = new int[k];
        return backtrack(jobs, workloads, jobs.length - 1, 0);
    }
    private int backtrack(int[] jobs, int[] workloads, int index, int maxLoad) {
        if (index < 0) return maxLoad;
        int limit = Integer.MAX_VALUE;
        for (int i = 0; i < workloads.length; i++) {
            workloads[i] += jobs[index];
            int newLoad = Math.max(maxLoad, workloads[i]);
            if (newLoad < limit) { 
                limit = Math.min(limit, backtrack(jobs, workloads, index - 1, newLoad));
            }
            workloads[i] -= jobs[index];
            if (workloads[i] == 0) break;
        }
        return limit;
    }
}

#include <stdio.h>
#include <limits.h>

void sort(int* arr, int size) {
    // Simple bubble sort implementation for descending order
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] < arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

void assignJobs(int* jobs, int* workloads, int index, int n, int k, int* minTime, int currentMax) {
    if (index == n) {
        if (currentMax < *minTime) {
            *minTime = currentMax;
        }
        return;
    }
    for (int i = 0; i < k; ++i) {
        workloads[i] += jobs[index];
        int newMax = currentMax > workloads[i] ? currentMax : workloads[i];
        if (newMax < *minTime) {
            assignJobs(jobs, workloads, index + 1, n, k, minTime, newMax);
        }
        workloads[i] -= jobs[index];
        if (workloads[i] == 0) break;
    }
}

int minimumTimeRequired(int* jobs, int jobsSize, int k) {
    sort(jobs, jobsSize);
    int workloads[k];
    for (int i = 0; i < k; ++i) workloads[i] = 0;
    int minTime = INT_MAX;
    assignJobs(jobs, workloads, 0, jobsSize, k, &minTime, 0);
    return minTime;
}

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.

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.

Python

def minimumTimeRequired(jobs, k):
    def canFinish(maxLoad):
        workloads = [0] * k
        def backtrack(index):
            if index == len(jobs):
                return True
            cur_job = jobs[index]
            for i in range(k):
                workloads[i] += cur_job
                if workloads[i] <= maxLoad and backtrack(index + 1):
                    return True
                workloads[i] -= cur_job
                if workloads[i] == 0:
                    break
            return False

        return backtrack(0)
    
    jobs.sort(reverse=True)
    left, right = max(jobs), sum(jobs)
    while left < right:
        mid = (left + right) // 2
        if canFinish(mid):
            right = mid
        else:
            left = mid + 1
    return left

Java

class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int low = jobs[jobs.length - 1], high = Arrays.stream(jobs).sum();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canFinish(jobs, k, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private boolean canFinish(int[] jobs, int k, int maxLoad) {
        int[] workloads = new int[k];
        return backtrack(jobs, workloads, jobs.length - 1, maxLoad);
    }

    private boolean backtrack(int[] jobs, int[] workloads, int index, int maxLoad) {
        if (index < 0) return true;
        int curJob = jobs[index];
        for (int i = 0; i < workloads.length; i++) {
            if (workloads[i] + curJob <= maxLoad) {
                workloads[i] += curJob;
                if (backtrack(jobs, workloads, index - 1, maxLoad)) {
                    return true;
                }
                workloads[i] -= curJob;
            }
            if (workloads[i] == 0) break;
        }
        return false;
    }
}

C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

bool canFinish(vector<int>& jobs, int k, int maxLoad) {
    vector<int> workloads(k, 0);
    return backtrack(jobs, workloads, jobs.size() - 1, maxLoad);
}

bool backtrack(vector<int>& jobs, vector<int>& workloads, int index, int maxLoad) {
    if (index < 0) return true;
    int currentJob = jobs[index];
    for (int i = 0; i < workloads.size(); i++) {
        if (workloads[i] + currentJob <= maxLoad) {
            workloads[i] += currentJob;
            if (backtrack(jobs, workloads, index - 1, maxLoad)) return true;
            workloads[i] -= currentJob;
        }
        if (workloads[i] == 0) break;
    }
    return false;
}

int minimumTimeRequired(vector<int>& jobs, int k) {
    sort(jobs.begin(), jobs.end());
    int low = jobs.back(), high = accumulate(jobs.begin(), jobs.end(), 0);
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canFinish(jobs, k, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

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.

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

func minimumTimeRequired(jobs []int, k int) int {
	cnt := make([]int, k)
	ans := 0x3f3f3f3f
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i] > jobs[j]
	})
	var dfs func(int)
	dfs = func(i int) {
		if i == len(jobs) {
			mx := slices.Max(cnt)
			ans = min(ans, mx)
			return
		}
		for j := 0; j < k; j++ {
			if cnt[j]+jobs[i] >= ans {
				continue
			}
			cnt[j] += jobs[i]
			dfs(i + 1)
			cnt[j] -= jobs[i]
			if cnt[j] == 0 {
				break
			}
		}
	}
	dfs(0)
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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(nklog(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	–

Approach

Complexity

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

–

Complexity analysis

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

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.

Find Minimum Time to Finish All Jobs solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Pruning

Approach 2: Binary Search with Feasibility Check

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Minimum Time to Finish All Jobs solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Pruning

Approach 2: Binary Search with Feasibility Check

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems