1723. Find Minimum Time to Finish All Jobs
DFS with pruning
T: O(k^n), n is jobs array size, but with lots pruning, beats 88%
S: O(n), recursion stack
class Solution {
int res = Integer.MAX_VALUE;
public int minimumTimeRequired(int[] jobs, int k) {
Arrays.sort(jobs); // prune1, put large one first, quick fail
reverse(jobs);
dfs(jobs, 0, new int[k]);
return res;
}
private void dfs(int[] jobs, int start, int[] bucket) {
if (start == jobs.length) {
res = Math.min(res, calMax(bucket));
return;
}
for (int i = 0; i < bucket.length; i++) {
if (i > 0 && bucket[i] == bucket[i - 1]) { // prune2: when try, pass duplicate data
continue;
}
if (calMax(bucket) >= res) { // prune3: if combination's max is bigger than result, pass
continue;
}
bucket[i] += jobs[start];
dfs(jobs, start+1, bucket);
bucket[i] -= jobs[start];
}
}
// cal in bucket, the max value now
private int calMax(int[] bucket) {
int max = 0;
for (int i = 0; i < bucket.length; i++) {
max = Math.max(max, bucket[i]);
}
return max;
}
private void reverse(int[] nums) {
int left = 0;
int right = nums.length-1;
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}Last updated
Was this helpful?