Problem Description

You are given two integers n (the number of workers) and an array jobs where jobs[i] is the time required to complete the i-th job.
Assign all jobs to the n workers such that each job is assigned to exactly one worker, and each worker can be assigned any number of jobs (including zero).
The working time of a worker is the sum of times of jobs assigned to them.
Your goal is to minimize the maximum working time among all workers after all jobs are assigned.
Return the minimum possible value of the maximum working time among the workers.
Constraints:

• 1 ≤ n ≤ 12
• 1 ≤ jobs.length ≤ 12
• 1 ≤ jobs[i] ≤ 10⁷

Thought Process

The problem is a classic example of job scheduling where we want to distribute jobs among workers to balance their workloads as evenly as possible. If we try every possible assignment, the number of combinations grows exponentially, making brute force impractical for larger inputs.
The key is to minimize the maximum workload among all workers. This is similar to the "minimum makespan" problem in scheduling. We need to find the best way to distribute jobs so that no single worker is overloaded more than necessary.
At first glance, one might consider distributing jobs in order, or assigning the largest job to the worker with the least current load. However, because of the small input size (n, jobs.length ≤ 12), we can use more advanced techniques like backtracking with pruning or binary search over the answer.

Solution Approach

We can use a binary search combined with backtracking to efficiently find the minimum possible maximum working time.

• Step 1: Binary Search over the Answer
  • We know the minimum possible maximum time is at least the largest single job (since someone has to do it), and at most the sum of all jobs (if one person does everything).
  • We perform binary search between these two bounds to find the smallest possible maximum working time for which an assignment is possible.
• Step 2: Backtracking Assignment Check
  • For a given maximum working time (midpoint in binary search), we try to assign jobs to workers so that no worker exceeds this time.
  • We use backtracking: for each job, try assigning it to any worker whose current load plus this job does not exceed the target maximum.
  • We prune the search by skipping assignments that would exceed the current maximum, or if a worker has the same load as a previous one (to avoid redundant states).
• Step 3: Optimization
  • Sort jobs in descending order before backtracking. Assigning larger jobs first increases the chance of pruning early.
  • Use a visited set or check to prevent assigning the same job configuration to workers with the same loads.

This approach efficiently narrows down the minimum possible maximum time using binary search, and uses recursive backtracking to check if a valid assignment exists for each candidate time.

Example Walkthrough

Sample Input:
n = 3, jobs = [3, 2, 3]

Step 1: The largest job is 3, and the sum is 8. So search between 3 and 8.
Step 2: Try mid = 5 (binary search midpoint).
Step 3: Backtracking to assign jobs:

• Assign 3 to worker 1 (load: [3,0,0])
• Assign next 3 to worker 2 (load: [3,3,0])
• Assign 2 to worker 1 (load: [5,3,0])
• All workers ≤ 5. Success!

• Assign 3 to worker 1 (load: [3,0,0])
• Assign next 3 to worker 2 (load: [3,3,0])
• Assign 2 to worker 1 (would be 5, exceeds 4), try worker 2 (would be 5), try worker 3 (load: [3,3,2])
• All jobs assigned, max load is 3, 3, 2 (max 3). This is valid, so try even lower.

• Assign 3 to worker 1 (load: [3,0,0])
• Assign next 3 to worker 2 (load: [3,3,0])
• Assign 2 to worker 1 (would be 5), worker 2 (would be 5), worker 3 (load: [3,3,2])
• All jobs assigned, max load is 3,3,2 (max 3). Success!

Time and Space Complexity

Brute-force:

• Try every job-to-worker assignment: O(n^k), where k is the number of jobs.
• For n=12, k=12, this is infeasible.

• Binary search: O(log S), where S is the sum of all jobs.
• Backtracking: In the worst case O(n^k), but with pruning and sorting, it's much faster in practice. For small n and k (≤12), this is acceptable.
• Space: O(n) for the worker loads array, and O(k) for recursion stack.

Overall, the solution is efficient for the given constraints.

Summary

We tackled the "Find Minimum Time to Finish All Jobs" problem by combining binary search and backtracking. The key insight is to search for the smallest possible maximum working time, and for each candidate, check if a valid assignment exists using recursive backtracking. Sorting jobs in descending order and pruning redundant states makes the solution efficient. This approach elegantly balances brute-force thoroughness with practical optimization, making it both correct and performant for the problem's constraints.

Code Implementation

class Solution:
    def minimumTimeRequired(self, jobs, k):
        jobs.sort(reverse=True)
        n = k
        res = sum(jobs)
        
        def can_assign(limit):
            workloads = [0] * n
            def backtrack(i):
                if i == len(jobs):
                    return True
                visited = set()
                for j in range(n):
                    if workloads[j] + jobs[i] > limit or workloads[j] in visited:
                        continue
                    visited.add(workloads[j])
                    workloads[j] += jobs[i]
                    if backtrack(i+1):
                        return True
                    workloads[j] -= jobs[i]
                    if workloads[j] == 0:
                        break
                return False
            return backtrack(0)
        
        left, right = max(jobs), sum(jobs)
        while left < right:
            mid = (left + right) // 2
            if can_assign(mid):
                right = mid
            else:
                left = mid + 1
        return left
      

class Solution {
public:
    bool canAssign(vector<int>& jobs, vector<int>& workloads, int idx, int limit) {
        if (idx == jobs.size()) return true;
        unordered_set<int> visited;
        for (int i = 0; i < workloads.size(); ++i) {
            if (workloads[i] + jobs[idx] > limit || visited.count(workloads[i])) continue;
            visited.insert(workloads[i]);
            workloads[i] += jobs[idx];
            if (canAssign(jobs, workloads, idx+1, limit)) return true;
            workloads[i] -= jobs[idx];
            if (workloads[i] == 0) break;
        }
        return false;
    }
    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.rbegin(), jobs.rend());
        int left = *max_element(jobs.begin(), jobs.end());
        int right = accumulate(jobs.begin(), jobs.end(), 0);
        while (left < right) {
            int mid = left + (right - left) / 2;
            vector<int> workloads(k, 0);
            if (canAssign(jobs, workloads, 0, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
      

class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int n = jobs.length;
        int left = jobs[n-1], right = 0;
        for (int j : jobs) right += j;
        int[] workloads = new int[k];
        Arrays.sort(jobs);
        for (int l = 0, r = n-1; l < r; l++, r--) {
            int tmp = jobs[l]; jobs[l] = jobs[r]; jobs[r] = tmp;
        }
        while (left < right) {
            int mid = (left + right) / 2;
            Arrays.fill(workloads, 0);
            if (canAssign(jobs, workloads, 0, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private boolean canAssign(int[] jobs, int[] workloads, int idx, int limit) {
        if (idx == jobs.length) return true;
        HashSet<Integer> visited = new HashSet<>();
        for (int i = 0; i < workloads.length; ++i) {
            if (workloads[i] + jobs[idx] > limit || visited.contains(workloads[i])) continue;
            visited.add(workloads[i]);
            workloads[i] += jobs[idx];
            if (canAssign(jobs, workloads, idx+1, limit)) return true;
            workloads[i] -= jobs[idx];
            if (workloads[i] == 0) break;
        }
        return false;
    }
}
      

var minimumTimeRequired = function(jobs, k) {
    jobs.sort((a, b) => b - a);
    let left = Math.max(...jobs), right = jobs.reduce((a,b) => a+b, 0);
    
    function canAssign(limit) {
        let workloads = new Array(k).fill(0);
        function backtrack(i) {
            if (i === jobs.length) return true;
            let visited = new Set();
            for (let j = 0; j < k; ++j) {
                if (workloads[j] + jobs[i] > limit || visited.has(workloads[j])) continue;
                visited.add(workloads[j]);
                workloads[j] += jobs[i];
                if (backtrack(i+1)) return true;
                workloads[j] -= jobs[i];
                if (workloads[j] === 0) break;
            }
            return false;
        }
        return backtrack(0);
    }
    
    while (left < right) {
        let mid = Math.floor((left+right)/2);
        if (canAssign(mid)) {
            right = mid;
        } else {
            left = mid+1;
        }
    }
    return left;
};