Formatted question description: https://leetcode.ca/all/1723.html

# 1723. Find Minimum Time to Finish All Jobs

## Level

Hard

## Description

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^7`

## Solution

Use dynamic programming with compressed states. Let `n`

be the length of `jobs`

. Create a 2D array `dp`

with `k + 1`

rows and `1 << n`

columns, where `dp[i][j]`

represents the minimum time required starting from job `i`

and mask `j`

.

Initialize `dp[k][(1 << n) - 1] = 0`

. Then for `i`

from `k - 1`

to 0 and for `mask`

from `(1 << length) - 2`

to 0, loop over all possible values `curr`

from 1 to `(1 << length) - 1`

. If `(curr & mask) == 0`

, then update `dp[i][mask]`

accordingly.

Finally, return `dp[0][0]`

.

```
class Solution {
public int minimumTimeRequired(int[] jobs, int k) {
int length = jobs.length;
int[][] dp = new int[k + 1][1 << length];
for (int i = 0; i <= k; i++)
Arrays.fill(dp[i], Integer.MAX_VALUE);
int[] times = new int[1 << length];
for (int mask = 0; mask < 1 << length; mask++) {
int time = 0;
for (int i = 0; i < length; i++) {
if ((mask & (1 << i)) != 0)
time += jobs[i];
}
times[mask] = time;
}
dp[k][(1 << length) - 1] = 0;
for (int i = k - 1; i >= 0; i--) {
for (int mask = (1 << length) - 2; mask >= 0; mask--) {
for (int curr = 1; curr < 1 << length; curr++) {
if ((curr & mask) == 0) {
int time = Math.max(times[curr], dp[i + 1][curr | mask]);
dp[i][mask] = Math.min(dp[i][mask], time);
}
}
}
}
return dp[0][0];
}
}
```