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.

Examples

Example 1

1
2
3

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2

1
2
3
4
5
6

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

Solution

Method 1 – Backtracking with Pruning

Intuition

Try all possible assignments of jobs to workers, but prune branches where the current assignment already exceeds the best found so far. Assign larger jobs first to maximize pruning.

Approach

  1. Sort jobs in descending order.
  2. Use a recursive function to assign each job to a worker.
  3. Track the maximum working time among all workers.
  4. Prune branches where the current max time is already worse than the best answer.
  5. Return the minimum possible maximum time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int ans = INT_MAX;
    void dfs(vector<int>& jobs, vector<int>& workers, int idx, int k) {
        if (idx == jobs.size()) {
            ans = min(ans, *max_element(workers.begin(), workers.end()));
            return;
        }
        for (int i = 0; i < k; ++i) {
            workers[i] += jobs[idx];
            int cur = *max_element(workers.begin(), workers.end());
            if (cur < ans)
                dfs(jobs, workers, idx + 1, k);
            workers[i] -= jobs[idx];
            if (workers[i] == 0) break;
        }
    }
    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.rbegin(), jobs.rend());
        vector<int> workers(k);
        dfs(jobs, workers, 0, k);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func minimumTimeRequired(jobs []int, k int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(jobs)))
    ans := 1 << 30
    workers := make([]int, k)
    var dfs func(idx int)
    dfs = func(idx int) {
        if idx == len(jobs) {
            max := 0
            for _, w := range workers {
                if w > max { max = w }
            }
            if max < ans { ans = max }
            return
        }
        for i := 0; i < k; i++ {
            workers[i] += jobs[idx]
            max := 0
            for _, w := range workers {
                if w > max { max = w }
            }
            if max < ans {
                dfs(idx + 1)
            }
            workers[i] -= jobs[idx]
            if workers[i] == 0 { break }
        }
    }
    dfs(0)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    int ans = Integer.MAX_VALUE;
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        reverse(jobs);
        int[] workers = new int[k];
        dfs(jobs, workers, 0, k);
        return ans;
    }
    void dfs(int[] jobs, int[] workers, int idx, int k) {
        if (idx == jobs.length) {
            int cur = Arrays.stream(workers).max().getAsInt();
            ans = Math.min(ans, cur);
            return;
        }
        for (int i = 0; i < k; ++i) {
            workers[i] += jobs[idx];
            int cur = Arrays.stream(workers).max().getAsInt();
            if (cur < ans) dfs(jobs, workers, idx + 1, k);
            workers[i] -= jobs[idx];
            if (workers[i] == 0) break;
        }
    }
    void reverse(int[] arr) {
        for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    var ans = Int.MAX_VALUE
    fun minimumTimeRequired(jobs: IntArray, k: Int): Int {
        jobs.sortDescending()
        val workers = IntArray(k)
        fun dfs(idx: Int) {
            if (idx == jobs.size) {
                ans = minOf(ans, workers.maxOrNull()!!)
                return
            }
            for (i in 0 until k) {
                workers[i] += jobs[idx]
                if (workers.maxOrNull()!! < ans) dfs(idx + 1)
                workers[i] -= jobs[idx]
                if (workers[i] == 0) break
            }
        }
        dfs(0)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def minimumTimeRequired(self, jobs: list[int], k: int) -> int:
        jobs.sort(reverse=True)
        ans = float('inf')
        workers = [0] * k
        def dfs(idx: int):
            nonlocal ans
            if idx == len(jobs):
                ans = min(ans, max(workers))
                return
            for i in range(k):
                workers[i] += jobs[idx]
                if max(workers) < ans:
                    dfs(idx + 1)
                workers[i] -= jobs[idx]
                if workers[i] == 0:
                    break
        dfs(0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn minimum_time_required(jobs: Vec<i32>, k: i32) -> i32 {
        let mut jobs = jobs;
        jobs.sort_by(|a, b| b.cmp(a));
        let mut ans = i32::MAX;
        let mut workers = vec![0; k as usize];
        fn dfs(jobs: &Vec<i32>, workers: &mut Vec<i32>, idx: usize, ans: &mut i32) {
            if idx == jobs.len() {
                *ans = (*ans).min(*workers.iter().max().unwrap());
                return;
            }
            for i in 0..workers.len() {
                workers[i] += jobs[idx];
                if *workers.iter().max().unwrap() < *ans {
                    dfs(jobs, workers, idx + 1, ans);
                }
                workers[i] -= jobs[idx];
                if workers[i] == 0 { break; }
            }
        }
        dfs(&jobs, &mut workers, 0, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minimumTimeRequired(jobs: number[], k: number): number {
        jobs.sort((a, b) => b - a);
        let ans = Infinity;
        const workers = Array(k).fill(0);
        const dfs = (idx: number) => {
            if (idx === jobs.length) {
                ans = Math.min(ans, Math.max(...workers));
                return;
            }
            for (let i = 0; i < k; i++) {
                workers[i] += jobs[idx];
                if (Math.max(...workers) < ans) dfs(idx + 1);
                workers[i] -= jobs[idx];
                if (workers[i] === 0) break;
            }
        };
        dfs(0);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k^n) where n is the number of jobs and k is the number of workers. The pruning and sorting help reduce the search space, but the worst case is exponential.
  • 🧺 Space complexity: O(n + k) for recursion stack and worker/job arrays.