1723. Find Minimum Time to Fini...
This page provides solutions for the leetcode problem 1723. Find Minimum Time to Finish All Jobs.
Problem Explanation
The problem is asking us to divide the jobs among workers in such a way the maximum working time of any worker is minimized.
Solution
For this problem, we need to consider all possible distribution possibilities. Therefore, we use the backtracking technique. More such problem can be found here.
- Java
class Solution {
private int min = Integer.MAX_VALUE;
public int minimumTimeRequired(int[] jobs, int k) {
backtrack(jobs, 0, new int[k]);
return min;
}
private void backtrack(int[] jobs, int index, int[] workers) {
if(index == jobs.length) {
min = Math.min(min, max(workers));
}
else {
for(int i = 0; i < workers.length; i++) {
if(i > 0 && workers[i] == workers[i - 1]) continue;
if(workers[i] + jobs[index] > min) continue;
workers[i] += jobs[index];
backtrack(jobs, index + 1, workers);
workers[i] -= jobs[index];
}
}
}
private int max(int[] array) {
int maxValue = Integer.MIN_VALUE;
for(int i = 0; i < array.length; i++) maxValue = Math.max(maxValue, array[i]);
return maxValue;
}
}
Complexity
Let be the length of the input array and be the number of workers.
Time Complexity
Each of the job has workers to choose from, so time complexity will be:
Space Complexity
Since there are jobs to assign to each worker, the stack size for the backtracking will go upto , so space complexity will be: