# Find Minimum Time to Finish All Jobs
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-time-to-finish-all-jobs
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Lyft](https://scaleengineer.com/companies/lyft), [PhonePe](https://scaleengineer.com/companies/phonepe), [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
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`

# Approaches
## Backtracking with Pruning
This approach explores all possible assignments of jobs to workers using recursion. For each job, we try to assign it to every worker. To make this feasible, we apply several key optimizations.
**Time:** O(k^n) in the worst case. While optimizations significantly reduce the search space, the upper bound remains exponential. For n=12, k=12, this can be slow but might pass due to the small constraints and effective pruning. · **Space:** O(n + k) for the recursion stack depth (n) and the workerTimes array (k).
**Pros:** Relatively simple to understand and implement compared to more advanced techniques.
**Cons:** The worst-case time complexity is very high, making it unsuitable for larger constraints.
### Explanation
The core idea is a recursive function, `backtrack(jobIndex, workerTimes)`, which tries to assign `jobs[jobIndex]` to one of the `k` workers. We apply several optimizations to make this feasible.

First, we sort the `jobs` array in descending order. This is a heuristic that often helps pruning work more effectively. Assigning larger jobs first means we are more likely to quickly create a high `workerTime`, which helps in pruning subsequent branches of the search tree that would exceed this time.

Second, we use pruning. We maintain a global variable `minMaxTime` that stores the minimum of the maximum worker times found so far. During the recursion, if assigning a job to a worker would make that worker's time greater than or equal to the current `minMaxTime`, we know this path cannot lead to a better solution, so we prune it.

Third, we break symmetry. Since the workers are indistinguishable, the assignment `{W1:[j1], W2:[j2]}` is the same as `{W1:[j2], W2:[j1]}`. We can avoid exploring these symmetric states by enforcing an order. A simple way is: when assigning a job, if we assign it to an empty worker (time = 0), we don't need to try assigning it to any other empty workers. This is because any assignment to another empty worker would lead to a state that is symmetric to one we are already exploring.

```java
class Solution {
    int minMaxTime = Integer.MAX_VALUE;

    public int minimumTimeRequired(int[] jobs, int k) {
        // Sort jobs in descending order for better pruning
        Arrays.sort(jobs);
        int[] reversedJobs = new int[jobs.length];
        for (int i = 0; i < jobs.length; i++) {
            reversedJobs[i] = jobs[jobs.length - 1 - i];
        }

        backtrack(reversedJobs, 0, new int[k]);
        return minMaxTime;
    }

    private void backtrack(int[] jobs, int jobIndex, int[] workerTimes) {
        if (jobIndex == jobs.length) {
            int currentMax = 0;
            for (int time : workerTimes) {
                currentMax = Math.max(currentMax, time);
            }
            minMaxTime = Math.min(minMaxTime, currentMax);
            return;
        }
        
        for (int i = 0; i < workerTimes.length; i++) {
            if (workerTimes[i] + jobs[jobIndex] >= minMaxTime) {
                continue;
            }
            
            workerTimes[i] += jobs[jobIndex];
            backtrack(jobs, jobIndex + 1, workerTimes);
            workerTimes[i] -= jobs[jobIndex];

            // Symmetry breaking: if this worker was empty,
            // no need to try other empty workers.
            if (workerTimes[i] == 0) {
                break;
            }
        }
    }
}
```
### Algorithm
*   The core idea is a recursive function, `backtrack(jobIndex, workerTimes)`, which tries to assign `jobs[jobIndex]` to one of the `k` workers.
*   **Algorithm Steps:**
    1.  Sort the `jobs` array in descending order. This helps in pruning more effectively, as assigning larger jobs first will quickly lead to exceeding any potential optimal maximum time.
    2.  Initialize an array `workerTimes` of size `k` to all zeros, representing the current total time for each worker.
    3.  Initialize a global variable `minMaxTime` to `Integer.MAX_VALUE` to store the minimum of the maximum worker times found so far.
    4.  Start the recursion with `backtrack(0, workerTimes)`.
    5.  Inside `backtrack(jobIndex, workerTimes)`:
        *   **Base Case:** If `jobIndex` equals the number of jobs, all jobs have been assigned. We find the maximum time in `workerTimes` and update `minMaxTime`.
        *   **Pruning:** Before assigning a job to a worker, check if their new time would exceed the current `minMaxTime`. If `workerTimes[i] + jobs[jobIndex] >= minMaxTime`, there's no need to explore this path further, so we skip this worker.
        *   **Recursive Step:** Iterate through each worker `i` from `0` to `k-1`.
            *   Assign `jobs[jobIndex]` to worker `i`.
            *   Recursively call `backtrack(jobIndex + 1, workerTimes)`.
            *   Undo the assignment (backtrack) to explore other possibilities.
        *   **Symmetry Breaking:** Since all workers are identical, assigning a job to any empty worker is equivalent. To avoid redundant computations, if we assign a job to a worker with `0` current time, we can stop trying other empty workers for this job. We `break` the loop after the recursive call for the first empty worker.

## Binary Search on Answer + Backtracking
This approach reframes the problem from an optimization problem ('find the minimum maximum') to a decision problem ('is it possible to achieve a maximum time of `X`?'). We can then binary search for the smallest `X` for which the answer is 'yes'.
**Time:** O(k^n * log(S)), where S is the sum of all job times. The log(S) factor comes from the binary search. The k^n is the worst-case complexity of the `isPossible` check. In practice, this is often faster than pure backtracking because the `limit` provides a very strong and fixed pruning condition. · **Space:** O(n + k) for the recursion stack and `workerTimes` array.
**Pros:** More structured than pure backtracking.; The fixed `limit` in the check function allows for aggressive pruning.
**Cons:** The worst-case time complexity is still high, although it performs well in practice.
### Explanation
This approach reframes the problem from an optimization problem ('find the minimum maximum') to a decision problem ('is it possible to achieve a maximum time of `X`?'). We can then binary search for the smallest `X` for which the answer is 'yes'.

The possible values for the minimum maximum working time are within a specific range. The lower bound is the largest single job time (as one worker must take it), and the upper bound is the sum of all job times (the case with one worker).

We perform a binary search on this range of possible answers. For each `mid` value in the binary search, we check if it's possible to assign all jobs such that no worker's time exceeds `mid`. This check is done by a helper function, `isPossible`, which itself uses a backtracking search. The key difference from the first approach is that the pruning condition is now a fixed `limit` (`mid`), which can make the search faster.

```java
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int[] reversedJobs = new int[jobs.length];
        int sum = 0;
        int maxJob = 0;
        for (int i = 0; i < jobs.length; i++) {
            reversedJobs[i] = jobs[jobs.length - 1 - i];
            sum += jobs[i];
            maxJob = Math.max(maxJob, jobs[i]);
        }

        int low = maxJob, high = sum;
        int ans = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(reversedJobs, k, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int[] jobs, int k, int limit) {
        return canAssign(jobs, 0, new int[k], limit);
    }

    private boolean canAssign(int[] jobs, int jobIndex, int[] workerTimes, int limit) {
        if (jobIndex == jobs.length) {
            return true;
        }

        for (int i = 0; i < workerTimes.length; i++) {
            if (workerTimes[i] + jobs[jobIndex] <= limit) {
                workerTimes[i] += jobs[jobIndex];
                if (canAssign(jobs, jobIndex + 1, workerTimes, limit)) {
                    return true;
                }
                workerTimes[i] -= jobs[jobIndex];
            }
            // Symmetry breaking
            if (workerTimes[i] == 0) {
                break;
            }
        }
        return false;
    }
}
```
### Algorithm
*   The possible values for the minimum maximum working time are within a specific range. The lower bound is the largest single job time, and the upper bound is the sum of all job times.
*   We perform a binary search on this range of possible answers. For each `mid` value, we check if it's possible to assign all jobs such that no worker's time exceeds `mid`.
*   **Algorithm Steps:**
    1.  Define the search range: `low = max(jobs)`, `high = sum(jobs)`.
    2.  Perform binary search:
        *   While `low <= high`, pick `mid = low + (high - low) / 2`.
        *   Call a helper function `isPossible(jobs, k, mid)` to check if an assignment is feasible with `mid` as the time limit.
        *   If `isPossible` is true, it means `mid` is a potential answer. We try for a better (smaller) one: `ans = mid`, `high = mid - 1`.
        *   If `isPossible` is false, `mid` is too small: `low = mid + 1`.
    3.  The `isPossible` function is implemented using a backtracking/DFS approach, similar to the first method.
*   **`isPossible(jobs, k, limit)` function:**
    1.  Sort `jobs` descendingly for better pruning.
    2.  Use a recursive function `canAssign(jobIndex, workerTimes, limit)`.
    3.  **Base Case:** If `jobIndex` reaches the end, all jobs are assigned within the `limit`. Return `true`.
    4.  **Recursive Step:** For the current `jobs[jobIndex]`, try to assign it to each worker `i`. If `workerTimes[i] + jobs[jobIndex] <= limit`, assign the job and recurse. If the recursive call returns `true`, we've found a valid assignment, so return `true` up the call stack. Backtrack if it fails.
    5.  Apply the same symmetry-breaking optimization as in the pure backtracking approach.

## Dynamic Programming with Bitmasking
Given the small constraint on the number of jobs (n <= 12), we can use dynamic programming with bitmasking to represent subsets of jobs. This approach directly calculates the minimum maximum time without binary search.
**Time:** O(k * 3^n). The outer loops run k and 2^n times. The inner loop iterates through all submasks. The total number of (sub, mask) pairs where sub is a submask of mask is 3^n. · **Space:** O(k * 2^n) for the DP table. This can be optimized to O(2^n) because dp[i] only depends on dp[i-1].
**Pros:** Provides a guaranteed polynomial-time solution with respect to `k` (but exponential in `n`).; It's more systematic than backtracking.
**Cons:** The 3^n complexity can be high, and the space complexity is also significant.
### Explanation
Given the small constraint on the number of jobs (n <= 12), we can use dynamic programming with bitmasking to represent subsets of jobs. This approach directly calculates the minimum maximum time without binary search.

We build the solution worker by worker. The state of our DP will involve the number of workers used and the subset of jobs completed.

**DP State:** `dp[i][mask]` represents the minimum possible maximum working time if we use `i` workers to complete the set of jobs represented by `mask`. A `1` at the `j`-th position in `mask` means job `j` is included.

First, we precompute an array `sum[mask]` that stores the total time for each subset of jobs. Then, we build our `dp` table. The base case is for `i=1` worker, where `dp[1][mask]` is simply `sum[mask]`. For `i > 1`, we compute `dp[i][mask]` by iterating through all submasks `sub` of `mask`. We assign the jobs in `sub` to the `i`-th worker and the jobs in `mask ^ sub` to the previous `i-1` workers. The maximum time for this split is `max(sum[sub], dp[i-1][mask ^ sub])`. We take the minimum over all possible submasks `sub`.

```java
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        int n = jobs.length;
        int[] sum = new int[1 << n];
        for (int mask = 1; mask < (1 << n); mask++) {
            // Find the lowest set bit (a job in the mask)
            int j = Integer.numberOfTrailingZeros(mask);
            int prevMask = mask ^ (1 << j);
            sum[mask] = sum[prevMask] + jobs[j];
        }

        int[][] dp = new int[k + 1][1 << n];
        
        // Base case: 1 worker
        for (int mask = 0; mask < (1 << n); mask++) {
            dp[1][mask] = sum[mask];
        }

        // Fill DP table for i = 2 to k workers
        for (int i = 2; i <= k; i++) {
            for (int mask = 1; mask < (1 << n); mask++) {
                dp[i][mask] = Integer.MAX_VALUE;
                // Iterate through all submasks of mask
                for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
                    int remainingMask = mask ^ sub;
                    int currentMax = Math.max(dp[i - 1][remainingMask], sum[sub]);
                    dp[i][mask] = Math.min(dp[i][mask], currentMax);
                }
            }
        }

        return dp[k][(1 << n) - 1];
    }
}
```
### Algorithm
*   **DP State:** `dp[i][mask]` represents the minimum possible maximum working time if we use `i` workers to complete the set of jobs represented by `mask`. A `1` at the `j`-th position in `mask` means job `j` is included.
*   **Precomputation:** First, we precompute an array `sum[mask]` that stores the total time for each subset of jobs. This can be done in O(n * 2^n) or O(2^n).
*   **Algorithm Steps:**
    1.  Precompute `sum[mask]` for all `2^n` masks.
    2.  Initialize a DP table `dp[k+1][1<<n]`.
    3.  **Base Case:** For one worker (`i=1`), the max time is just the sum of jobs in the subset: `dp[1][mask] = sum[mask]`.
    4.  **Transition:** We iterate from `i = 2` to `k` workers. To compute `dp[i][mask]`, we consider all possible ways to form the `i`-th worker's assignment. We can give a subset of jobs `sub` (a submask of `mask`) to the `i`-th worker. The remaining `i-1` workers must handle the jobs in `mask \ sub`. The maximum time for this specific split is `max(sum[sub], dp[i-1][mask ^ sub])`. We want to find the `sub` that minimizes this value.
        `dp[i][mask] = min( max(dp[i-1][mask ^ sub], sum[sub]) )` for all non-empty proper submasks `sub` of `mask`.
    5.  The final answer is `dp[k][(1<<n) - 1]`.

## Binary Search + DP with Bitmasking
This is the most efficient approach, combining the binary search strategy with a fast DP-based check for the decision problem.
**Time:** O(n * 2^n * log(S)), where S is the sum of job times. The `isPossible` check takes O(n * 2^n) and it's called log(S) times. · **Space:** O(2^n) for the DP table used in the `isPossible` check.
**Pros:** The most efficient known algorithm for this problem's constraints.; It combines two powerful techniques to achieve a much better time complexity.
**Cons:** More complex to conceptualize and implement correctly compared to the other approaches.
### Explanation
This is the most efficient approach, combining the binary search strategy with a fast DP-based check for the decision problem.

Similar to the second approach, we binary search for the minimum possible maximum time, `limit`. The core of this method is a highly efficient `isPossible(limit)` check using dynamic programming.

The decision problem is: 'Is it possible to partition the `jobs` array into `k` or fewer subsets, such that the sum of each subset does not exceed `limit`?'

We can solve this with DP. Let `dp[mask]` store the time taken by the last worker for an optimal partition of jobs in `mask`, and `workers[mask]` store the number of workers needed. We want to minimize `workers`, and then `dp` as a tie-breaker.

We iterate through each `mask` from 1 to `(1<<n)-1`. For each job `j` in the mask, we look at the state for `mask ^ (1<<j)`. We try to add job `j` to this previous state. If we can add it to the last worker without exceeding `limit`, we do so. Otherwise, we must start a new worker. We update the state for `mask` if we find a better partition (fewer workers, or same workers with less time on the last one).

After computing the DP table, we check if `workers[(1<<n)-1]` is at most `k`. If so, the `limit` is achievable.

```java
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        int n = jobs.length;
        int sum = 0;
        int maxJob = 0;
        for (int job : jobs) {
            sum += job;
            maxJob = Math.max(maxJob, job);
        }

        int low = maxJob, high = sum;
        int ans = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(jobs, k, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int[] jobs, int k, int limit) {
        int n = jobs.length;
        int[] dp = new int[1 << n]; // Stores time of last worker
        int[] workers = new int[1 << n]; // Stores num of workers
        Arrays.fill(dp, Integer.MAX_VALUE);
        Arrays.fill(workers, Integer.MAX_VALUE);
        dp[0] = 0;
        workers[0] = 1;

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    int prevMask = mask ^ (1 << j);
                    if (workers[prevMask] == Integer.MAX_VALUE) continue;

                    // Option 1: Add to the last worker of the previous state
                    if (dp[prevMask] + jobs[j] <= limit) {
                        if (workers[prevMask] < workers[mask] || 
                           (workers[prevMask] == workers[mask] && dp[prevMask] + jobs[j] < dp[mask])) {
                            workers[mask] = workers[prevMask];
                            dp[mask] = dp[prevMask] + jobs[j];
                        }
                    } 
                    // Option 2: Start a new worker
                    else {
                        if (workers[prevMask] + 1 < workers[mask] ||
                           (workers[prevMask] + 1 == workers[mask] && jobs[j] < dp[mask])) {
                            workers[mask] = workers[prevMask] + 1;
                            dp[mask] = jobs[j];
                        }
                    }
                }
            }
        }
        return workers[(1 << n) - 1] <= k;
    }
}
```
### Algorithm
*   Similar to the second approach, we binary search for the minimum possible maximum time, `limit`.
*   **Decision Problem:** 'Is it possible to partition the `jobs` array into `k` or fewer subsets, such that the sum of each subset does not exceed `limit`?'
*   **DP State for `isPossible`:** We use a DP table `dp[mask]` to store information about partitioning the jobs in `mask`. A simple and effective state is `dp[mask] = (workers_needed, time_of_last_worker)`. We aim to minimize `workers_needed` first, and then `time_of_last_worker` as a tie-breaker.
*   **Algorithm Steps:**
    1.  Perform binary search on the answer `limit` in the range `[max(jobs), sum(jobs)]`.
    2.  For each `limit`, call `isPossible(jobs, k, limit)`.
*   **`isPossible(jobs, k, limit)` function:**
    1.  Define `dp[mask]` as a pair `{num_workers, last_worker_time}`.
    2.  Initialize `dp[0] = {1, 0}`. All other `dp[mask]` are initialized to an invalid state like `{k+1, 0}`.
    3.  Iterate `mask` from `1` to `(1<<n) - 1`.
    4.  For each `mask`, iterate through each job `j` that is part of the `mask`.
    5.  Let `prev_mask = mask ^ (1 << j)`. Get the state `dp[prev_mask]`.
    6.  Consider adding job `j` to the partition for `prev_mask`. We can either add it to the last worker if time permits, or start a new worker.
    7.  Update `dp[mask]` with the lexicographically smaller of the new state and its current value.
    8.  After filling the DP table, if `dp[(1<<n) - 1].num_workers <= k`, return `true`.

# Solutions
### Java

```java
class Solution { private int [] cnt ; private int ans ; private int [] jobs ; private int k ; public int minimumTimeRequired ( int [] jobs , int k ) { this . k = k ; Arrays . sort ( jobs ); for ( int i = 0 , j = jobs . length - 1 ; i < j ; ++ i , -- j ) { int t = jobs [ i ]; jobs [ i ] = jobs [ j ]; jobs [ j ] = t ; } this . jobs = jobs ; cnt = new int [ k ]; ans = 0x3f3f3f3f ; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i == jobs . length ) { int mx = 0 ; for ( int v : cnt ) { mx = Math . max ( mx , v ); } ans = Math . min ( ans , mx ); return ; } for ( int 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 ; } } } }
```

### CPP

```cpp
class Solution { public: int ans ; int minimumTimeRequired ( vector < int >& jobs , int k ) { vector < int > cnt ( k ); ans = 0x3f3f3f3f ; sort ( jobs . begin (), jobs . end (), greater < int > ()); dfs ( 0 , k , jobs , cnt ); return ans ; } void dfs ( int i , int k , vector < int >& jobs , vector < int >& cnt ) { if ( i == jobs . size ()) { ans = min ( ans , * max_element ( cnt . begin (), cnt . end ())); return ; } for ( int j = 0 ; j < k ; ++ j ) { if ( cnt [ j ] + jobs [ i ] >= ans ) continue ; cnt [ j ] += jobs [ i ]; dfs ( i + 1 , k , jobs , cnt ); cnt [ j ] -= jobs [ i ]; if ( cnt [ j ] == 0 ) break ; } } };
```

### Python

```python
class Solution : def minimumTimeRequired ( self , jobs : List [ int ], k : int ) -> int : def dfs ( i ): nonlocal ans if i == len ( jobs ): ans = min ( ans , max ( cnt )) return for j in range ( k ): if cnt [ j ] + jobs [ i ] >= ans : continue cnt [ j ] += jobs [ i ] dfs ( i + 1 ) cnt [ j ] -= jobs [ i ] if cnt [ j ] == 0 : break cnt = [ 0 ] * k jobs . sort ( reverse = True ) ans = inf dfs ( 0 ) return ans
```