代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 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 <= 2000tasks[i].length == 31 <= starti, endi <= 20001 <= durationi <= endi - starti + 1 我们观察发现，题目相当于在每一个区间 $[start,..,end]$ 中，选择 $duration$ 个整数时间点，使得总共选择的整数时间点最少。
因此，我们可以先对 $tasks$ 按照结束时间 $end$ 从小到大排序。然后贪心地进行选择，对于每一个任务，我们从结束时间 $end$ 开始，从后往前选择尽可能靠后的点，这样这些点更有可能被后面的任务重复利用。
我们在实现上，可以用一个长度为 $2010$ 的数组 $vis$ 记录每个时间点是否被选择过。然后对于每一个任务，我们先统计 $[start,..,end]$ 区间内已经被选择过的点的个数 $cnt$，然后从后往前选择 $duration - cnt$ 个点，同时记录选择的点的个数 $ans$ 以及更新 $vis$ 数组。
最后，我们返回 $ans$ 即可。
时间复杂度 $O(n \times \log n + n \times m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为 $tasks$ 的长度和 $vis$ 数组的长度。本题中 $m = 2010$。
class Solution:
def findMinimumTime(self, tasks: List[List[int]]) -> int:
tasks.sort(key=lambda x: x[1])
vis = [0] * 2010
ans = 0
for start, end, duration in tasks:
duration -= sum(vis[start : end + 1])
i = end
while i >= start and duration > 0:
if not vis[i]:
duration -= 1
vis[i] = 1
ans += 1
i -= 1
return ans
class Solution {
public int findMinimumTime(int[][] tasks) {
Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
int[] vis = new int[2010];
int ans = 0;
for (var task : tasks) {
int start = task[0], end = task[1], duration = task[2];
for (int i = start; i <= end; ++i) {
duration -= vis[i];
}
for (int i = end; i >= start && duration > 0; --i) {
if (vis[i] == 0) {
--duration;
ans += vis[i] = 1;
}
}
}
return ans;
}
}
class Solution {
public:
int findMinimumTime(vector<vector<int>>& tasks) {
sort(tasks.begin(), tasks.end(), [&](auto& a, auto& b) { return a[1] < b[1]; });
bitset<2010> vis;
int ans = 0;
for (auto& task : tasks) {
int start = task[0], end = task[1], duration = task[2];
for (int i = start; i <= end; ++i) {
duration -= vis[i];
}
for (int i = end; i >= start && duration > 0; --i) {
if (!vis[i]) {
--duration;
ans += vis[i] = 1;
}
}
}
return ans;
}
};
func findMinimumTime(tasks [][]int) (ans int) {
sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
vis := [2010]int{}
for _, task := range tasks {
start, end, duration := task[0], task[1], task[2]
for _, x := range vis[start : end+1] {
duration -= x
}
for i := end; i >= start && duration > 0; i-- {
if vis[i] == 0 {
vis[i] = 1
duration--
ans++
}
}
}
return
}
function findMinimumTime(tasks: number[][]): number {
tasks.sort((a, b) => a[1] - b[1]);
const vis = new Array(2010).fill(0);
let ans = 0;
for (let [start, end, duration] of tasks) {
for (let i = start; i <= end; ++i) {
duration -= vis[i];
}
for (let i = end; i >= start && duration > 0; --i) {
if (vis[i] === 0) {
--duration;
ans += vis[i] = 1;
}
}
}
return ans;
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。