class Solution {
public:
int findMinimumTime(vector<vector<int>>& tasks) {
}
};
6318. 完成所有任务的最少时间
你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 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 原站题解
cpp 解法, 执行用时: 52 ms, 内存消耗: 42 MB, 提交时间: 2024-05-15 07:39:19
class Solution {
public:
int findMinimumTime(vector<vector<int>>& tasks) {
ranges::sort(tasks, [](auto& a, auto& b) { return a[1] < b[1]; });
int ans = 0;
vector<int> run(tasks.back()[1] + 1);
for (auto& t : tasks) {
int start = t[0], end = t[1], d = t[2];
d -= reduce(run.begin() + start, run.begin() + end + 1); // 去掉运行中的时间点
for (int i = end; d > 0; i--) { // 剩余的 d 填充区间后缀
if (!run[i]) {
run[i] = true; // 运行
d--;
ans++;
}
}
}
return ans;
}
};
cpp 解法, 执行用时: 52 ms, 内存消耗: 41.9 MB, 提交时间: 2024-05-15 07:38:45
class Solution {
public:
int findMinimumTime(vector<vector<int>>& tasks) {
ranges::sort(tasks, [](auto& a, auto& b) { return a[1] < b[1]; });
// 栈中保存闭区间左右端点，栈底到栈顶的区间长度的和
vector<array<int, 3>> st{{-2, -2, 0}}; // 哨兵，保证不和任何区间相交
for (auto& t : tasks) {
int start = t[0], end = t[1], d = t[2];
auto [_, r, s] = *--lower_bound(st.begin(), st.end(), start, [](const auto& a, int b) {
return a[0] < b;
});
d -= st.back()[2] - s; // 去掉运行中的时间点
if (start <= r) { // start 在区间 st[i] 内
d -= r - start + 1; // 去掉运行中的时间点
}
if (d <= 0) {
continue;
}
while (end - st.back()[1] <= d) { // 剩余的 d 填充区间后缀
auto [l, r, _] = st.back();
st.pop_back();
d += r - l + 1; // 合并区间
}
st.push_back({end - d + 1, end, st.back()[2] + d});
}
return st.back()[2];
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-03-13 09:32:39
class Solution:
def findMinimumTime(self, tasks: List[List[int]]) -> int:
tasks.sort(key=lambda t: t[1])
st = [(-2, -2, 0)] # 闭区间左右端点，栈底到栈顶的区间长度的和
for start, end, d in tasks:
_, r, s = st[bisect_left(st, (start,)) - 1]
d -= st[-1][2] - s # 去掉运行中的时间点
if start <= r: # start 在区间 st[i] 内
d -= r - start + 1 # 去掉运行中的时间点
if d <= 0: continue
while end - st[-1][1] <= d: # 剩余的 d 填充区间后缀
l, r, _ = st.pop()
d += r - l + 1 # 合并区间
st.append((end - d + 1, end, st[-1][2] + d))
return st[-1][2]
java 解法, 执行用时: 7 ms, 内存消耗: 42 MB, 提交时间: 2023-03-13 09:32:19
class Solution {
public int findMinimumTime(int[][] tasks) {
Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
var st = new ArrayList<int[]>();
st.add(new int[]{-2, -2, 0}); // 闭区间左右端点，栈底到栈顶的区间长度的和
for (var t : tasks) {
int start = t[0], end = t[1], d = t[2];
var e = st.get(lowerBound(st, start) - 1);
d -= st.get(st.size() - 1)[2] - e[2]; // 去掉运行中的时间点
if (start <= e[1]) // start 在区间 st[i] 内
d -= e[1] - start + 1; // 去掉运行中的时间点
if (d <= 0) continue;
while (end - st.get(st.size() - 1)[1] <= d) { // 剩余的 d 填充区间后缀
e = st.remove(st.size() - 1);
d += e[1] - e[0] + 1; // 合并区间
}
st.add(new int[]{end - d + 1, end, st.get(st.size() - 1)[2] + d});
}
return st.get(st.size() - 1)[2];
}
// 开区间写法
private int lowerBound(List<int[]> st, int target) {
int left = -1, right = st.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// st[left] < target
// st[right] >= target
int mid = (left + right) >>> 1;
if (st.get(mid)[0] < target)
left = mid; // 范围缩小到 (mid, right)
else
right = mid; // 范围缩小到 (left, mid)
}
return right; // 或者 left+1
}
}
golang 解法, 执行用时: 24 ms, 内存消耗: 6.3 MB, 提交时间: 2023-03-13 09:32:07
func findMinimumTime(tasks [][]int) int {
sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
type tuple struct{ l, r, s int }
st := []tuple{{-2, -2, 0}} // 闭区间左右端点，栈底到栈顶的区间长度的和
for _, p := range tasks {
start, end, d := p[0], p[1], p[2]
i := sort.Search(len(st), func(i int) bool { return st[i].l >= start }) - 1
d -= st[len(st)-1].s - st[i].s // 去掉运行中的时间点
if start <= st[i].r { // start 在区间 st[i] 内
d -= st[i].r - start + 1 // 去掉运行中的时间点
}
if d <= 0 {
continue
}
for end-st[len(st)-1].r <= d { // 剩余的 d 填充区间后缀
top := st[len(st)-1]
st = st[:len(st)-1]
d += top.r - top.l + 1 // 合并区间
}
st = append(st, tuple{end - d + 1, end, st[len(st)-1].s + d})
}
return st[len(st)-1].s
}
golang 解法, 执行用时: 48 ms, 内存消耗: 6.4 MB, 提交时间: 2023-03-13 09:31:34
func findMinimumTime(tasks [][]int) (ans int) {
sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
run := make([]bool, tasks[len(tasks)-1][1]+1)
for _, t := range tasks {
start, end, d := t[0], t[1], t[2]
for _, b := range run[start : end+1] { // 去掉运行中的时间点
if b {
d--
}
}
for i := end; d > 0; i-- { // 剩余的 d 填充区间后缀
if !run[i] {
run[i] = true
d--
ans++
}
}
}
return
}
java 解法, 执行用时: 18 ms, 内存消耗: 41.9 MB, 提交时间: 2023-03-13 09:31:19
class Solution {
public int findMinimumTime(int[][] tasks) {
Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
int ans = 0;
var run = new boolean[tasks[tasks.length - 1][1] + 1];
for (var t : tasks) {
int start = t[0], end = t[1], d = t[2];
for (int i = start; i <= end; ++i)
if (run[i]) --d; // 去掉运行中的时间点
for (int i = end; d > 0; --i) // 剩余的 d 填充区间后缀
if (!run[i]) {
run[i] = true;
--d;
++ans;
}
}
return ans;
}
}
python3 解法, 执行用时: 272 ms, 内存消耗: 15.9 MB, 提交时间: 2023-03-13 09:30:58
'''
暴力
'''
class Solution:
def findMinimumTime(self, tasks: List[List[int]]) -> int:
tasks.sort(key=lambda t: t[1])
run = [False] * (tasks[-1][1] + 1)
for start, end, d in tasks:
d -= sum(run[start:end + 1]) # 去掉运行中的时间点
if d > 0:
for i in range(end, start - 1, -1): # 剩余的 d 填充区间后缀
if run[i]: continue
run[i] = True
d -= 1
if d == 0: break
return sum(run)