前言
今天也是很无精打采的一天,早上看到这道题,都有点懵逼,开始也不懂如何入手,既然自己搞不定,就顺便测试了一下AI吧,测试了通义千问和文心一言,把题目拿去那里问,可以把解题思路写出来,代码也写了,但是我拿到AI的代码来运行,发现2个平台的代码都是运行不通过的,说明AI对这种算法题,是不对的,AI测试了一轮,只好自己去理解了,看了一下AI的代码,给自己一些思路,按照自己的思路去优化代码最终通过。
题目
2589. 完成所有任务的最少时间
你有一台电脑,它可以 同时 运行无数个任务。给你一个二维整数数组 tasks
,其中 tasks[i] = [starti, endi, durationi]
表示第 i
个任务需要在 闭区间 时间段 [starti, endi]
内运行 durationi
个整数时间点(但不需要连续)。
当电脑需要运行任务时,你可以打开电脑,如果空闲时,你可以将电脑关闭。
请你返回完成所有任务的情况下,电脑最少需要运行多少秒。
示例 1:
输入:tasks = [[2,3,1],[4,5,1],[1,5,2]] 输出:2 解释: - 第一个任务在闭区间 [2, 2] 运行。 - 第二个任务在闭区间 [5, 5] 运行。 - 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。 电脑总共运行 2 个整数时间点。
示例 2:
输入:tasks = [[1,3,2],[2,5,3],[5,6,2]] 输出:4 解释: - 第一个任务在闭区间 [2, 3] 运行 - 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。 - 第三个任务在闭区间 [5, 6] 运行。 电脑总共运行 4 个整数时间点。
提示:
1 <= tasks.length <= 2000
tasks[i].length == 3
1 <= starti, endi <= 2000
1 <= durationi <= endi - starti + 1
解题思路
- 按照end时间进行排序
- mark数组标记那些时刻已经被使用了。
- 遍历每一个task,按照该task的执行时间段从大到小占用时刻,直到满足时间占用==duration为止。
代码
class Solution {public int findMinimumTime(int[][] tasks) {// 按照结束时间排序Arrays.sort(tasks, Comparator.comparingInt(a -> a[1]));int ans = 0; // 电脑的总运行时间boolean[] used = new boolean[2024];for (int[] task : tasks) {int start = task[0];int end = task[1];int duration = task[2];for (int j = start; j <= end; j++) {if (used[j]) {duration--;}}for (int j = end; duration > 0; j--) {if (!used[j]) {ans++;used[j] = true;duration--;}}}return ans;}
}
每一次的记录,都是一次学习。