完成所有工作的最短时间 II

/*
 * Leetcode 2323: 完成所有工作的最短时间 II
 * 题目思路：
 * 使用Java Stream API优化代码，先排序，然后二分查找最小的最大工作时间，再用回溯法验证。
 */
import java.util.Arrays;

public class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int left = jobs[jobs.length - 1];
        int right = Arrays.stream(jobs).sum();
        while (left < right) {
            int mid = (left + right) / 2;
            if (canFinish(jobs, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canFinish(int[] jobs, int k, int limit) {
        int[] workers = new int[k];
        return backtrack(jobs, workers, jobs.length - 1, limit);
    }

    private boolean backtrack(int[] jobs, int[] workers, int idx, int limit) {
        if (idx < 0) return true;
        int curJob = jobs[idx];
        for (int i = 0; i < workers.length; i++) {
            if (workers[i] + curJob <= limit) {
                workers[i] += curJob;
                if (backtrack(jobs, workers, idx - 1, limit)) return true;
                workers[i] -= curJob;
            }
            if (workers[i] == 0) break;
        }
        return false;
    }
}