LeetCode 1723: Find Minimum Time to Finish All Jobs

Explanation:

To solve this problem, we can use binary search along with backtracking. We can represent the search space using binary search as the minimum and maximum possible values for the maximum working time. Then, we recursively try to assign jobs to workers such that the working time of each worker does not exceed the current maximum working time. If we are able to assign all jobs with the current maximum working time or less, we update our result and continue searching for a smaller maximum working time. If we cannot assign all jobs with the current maximum working time, we backtrack and try a larger maximum working time.

Algorithm:

1. Perform a binary search on the possible range of maximum working times.
2. For each mid value in the binary search, try to assign jobs to workers in a backtracking manner.
3. Update the result if we can successfully assign all jobs with the current maximum working time.
4. Continue the binary search for a smaller maximum working time if possible, else go for a larger maximum working time.

Time Complexity:

The time complexity of this approach is O(n * 2^k * log(sum)), where n is the number of jobs, k is the number of workers, and sum is the total sum of job times.

Space Complexity:

The space complexity is O(n) for the recursive backtracking stack.

: :

class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        int n = jobs.length;
        int[] workers = new int[k];
        Arrays.fill(workers, 0);
        int[] result = new int[]{Integer.MAX_VALUE};
        backtrack(jobs, workers, 0, result);
        return result[0];
    }
    
    private void backtrack(int[] jobs, int[] workers, int index, int[] result) {
        if (index == jobs.length) {
            int max = Arrays.stream(workers).max().getAsInt();
            result[0] = Math.min(result[0], max);
            return;
        }
        
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < workers.length; i++) {
            if (seen.contains(workers[i]) || workers[i] + jobs[index] >= result[0]) continue;
            seen.add(workers[i]);
            workers[i] += jobs[index];
            backtrack(jobs, workers, index + 1, result);
            workers[i] -= jobs[index];
        }
    }
}