LeetCode 1986. The minimum working time to complete the task is one question per day

Problem description

You are arranged n  A mission . The duration of the task is n  Array of integers for  tasks  Express , The first i  Tasks cost  tasks[i]  Hours to complete . One Working hours   in , You can at most   Continuous work  sessionTime  Hours , Then take a rest .

You need to complete the given task according to the following conditions ：

If you start a task at a certain time , You need to The same   Time period to complete it .
After completing a task , You can Immediately   Start a new task .
You can press In any order   To complete the task .
Here you are.  tasks and  sessionTime , Please follow the above requirements , Return to what is needed to complete all tasks   least   Count   Working hours  .

Test data guarantee  sessionTime Greater than or equal to  tasks[i]  Medium   Maximum  .

Example 1：

Input ：tasks = [1,2,3], sessionTime = 3
Output ：2
explain ： You can complete all tasks in two working hours .
- The first working period ： Complete the first and second tasks , cost 1 + 2 = 3 Hours .
- The second working period ： Complete the third task , cost 3 Hours .
Example 2：

Input ：tasks = [3,1,3,1,1], sessionTime = 8
Output ：2
explain ： You can complete all tasks in two working hours .
- The first working period ： Complete all tasks except the last one , cost 3 + 1 + 3 + 1 = 8 Hours .
- The second working period , Finish the last task , cost 1 Hours .
Example 3：

Input ：tasks = [1,2,3,4,5], sessionTime = 15
Output ：1
explain ： You can complete all tasks in one working time .
 

Tips ：

n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimum-number-of-work-sessions-to-finish-the-tasks
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        Arrays.sort(tasks);
        int n = tasks.length;

        int left = 1;
        int right = n;
        while(left < right){
            int mid = (left + right) >> 1;
            int[] timeParagraph = new int[mid];
            if(dfs(n - 1,tasks,timeParagraph,mid,sessionTime)){
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean dfs(int index,int[] tasks,int[] timeParagraph,int mid,int sessionTime){
        if(index == -1) return true;

        boolean[] visible = new boolean[sessionTime + 1];
        // Traverse every time segment 
        for(int i = 0;i < mid;i++){
            // If the value of the previous bucket has already appeared , You can skip the bucket , Try to put into the next bucket 
            if(visible[timeParagraph[i]]) continue;
            visible[timeParagraph[i]] = true;

            int t = timeParagraph[i] + tasks[index];
            if(t <= sessionTime){
                timeParagraph[i] = t;
                if(dfs(index - 1,tasks,timeParagraph,mid,sessionTime)) return true;
                timeParagraph[i] -= tasks[index];
            }
        }
        return false;
    }
}