1986. 完成任务的最少工作时间段Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个工作时间段中，你可以至多连续工作 sessionTime 个小时，然后休息一会儿。

你需要按照如下条件完成给定任务：

如果你在某一个时间段开始一个任务，你需要在同一个时间段完成它。
完成一个任务后，你可以立马开始一个新的任务。
你可以按任意顺序完成任务。给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的最少数目的工作时间段。

测试数据保证 sessionTime 大于等于 tasks[i] 中的最大值。

示例 1：

输入：tasks = [1,2,3], sessionTime = 3
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。

示例 2：

输入：tasks = [3,1,3,1,1], sessionTime = 8
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。
- 第二个工作时间段，完成最后一个任务，花费 1 小时。

示例 3：

输入：tasks = [1,2,3,4,5], sessionTime = 15
输出：1
解释：你可以在一个工作时间段以内完成所有任务。

提示：

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

# 思路

暴力遍历所有可能性

# 解法

    class Solution {
        public int minSessions(int[] tasks, int sessionTime) {
            // 枚举所有可能的时段个数
            for (int cnt = 1; cnt <= tasks.length; cnt++) {
                if (trySessionTime(tasks, sessionTime, cnt)) {
                    return cnt;
                }
            }
            return tasks.length;
        }

        boolean isOk;

        private boolean trySessionTime(int[] tasks, int sessionTime, int cnt) {
            // 判断cnt个sessionTime是否可以装下所有的tasks
            int[] sessions = new int[cnt];
            isOk = false;
            check(tasks, sessionTime, 0, sessions);
            return isOk;
        }

        private void check(int[] tasks, int sessionTime, int index, int[] sessions) {
            if (index == tasks.length) {
                isOk = true;
                return;
            }
            // 把第index个任务放到不同sessions中进行枚举
            int task = tasks[index];
            for (int i = 0; i < Math.min(index + 1, sessions.length); i++) { // 任务数比session少的时候不去枚举后面的session
                if (sessions[i] + task <= sessionTime) {
                    sessions[i] += task;
                    check(tasks, sessionTime, index + 1, sessions);
                    sessions[i] -= task;
                }
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 总结

分析出几种情况，然后分别对各个情况实现

#Java