当前位置：首页 > article >正文

算法---完成任务的最少工作时间段

article 2025/1/16 0:47:27

题目：

你被安排了 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-work-sessions-to-finish-the-tasks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方法：

    fun minSessions(tasks: IntArray, sessionTime: Int): Int {


        //任务的长度
        val size = tasks.size
        //计算size长度的二进制对应的十进制
        val dpSize = 1 shl size
        //创建数组空间 每个元素都是2个 第0位表示当前的占用多少个工作段  第一位表示最后一段已经用了多少工作时间
        var mask = Array(dpSize) { IntArray(2) { Int.MAX_VALUE } }

        mask[0] = intArrayOf(1, 0)

        for (i in 1 until dpSize) {
            var j = 0
            while ((1 shl j) <= i) {
                if (i and (1 shl j) == 0){
                    j++
                    continue
                }
                //如果最后一个工作段放不下了
                if (mask[i xor (1 shl j)][1] + tasks[j] > sessionTime) {
                    if (mask[i xor (1 shl j)][0] + 1 <= mask[i][0]) {
                        mask[i][0] = mask[i xor (1 shl j)][0] + 1
                        mask[i][1] = mask[i][1].coerceAtMost(tasks[j])
                    }
                } else {
                    //最后一个总做段还可以放下 如果当前用的时间段比之前小 更新
                    if (mask[i xor (1 shl j)][0]  <= mask[i][0]) {
                        mask[i][0] = mask[i xor (1 shl j)][0]
                        mask[i][1] = mask[i][1].coerceAtMost(mask[i xor (1 shl j)][1] + tasks[j])
                    }
                }
                j++
            }
        }
        return mask[mask.size - 1][0]
    }