class Solution {
public:
int processTasks(vector<vector<int>>& tasks) {
}
};
LCP 32. 批量处理任务
某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks，表示完成该任务的时间范围为起始时间 start 至结束时间 end 之间，需要计算机投入 period 的时长，注意：
period 可为不连续时间处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。
示例 1：
输入：
tasks = [[1,3,2],[2,5,3],[5,6,2]]输出：
4解释： tasks[0] 选择时间点 2、3； tasks[1] 选择时间点 2、3、5； tasks[2] 选择时间点 5、6； 因此计算机仅需在时间点 2、3、5、6 四个时刻保持开机即可完成任务。
示例 2：
输入：
tasks = [[2,3,1],[5,5,1],[5,6,2]]输出：
3解释： tasks[0] 选择时间点 2 或 3； tasks[1] 选择时间点 5； tasks[2] 选择时间点 5、6； 因此计算机仅需在时间点 2、5、6 或 3、5、6 三个时刻保持开机即可完成任务。
提示：
2 <= tasks.length <= 10^5tasks[i].length == 30 <= tasks[i][0] <= tasks[i][1] <= 10^91 <= tasks[i][2] <= tasks[i][1]-tasks[i][0] + 1原站题解
golang 解法, 执行用时: 544 ms, 内存消耗: 23.2 MB, 提交时间: 2023-09-26 20:19:05
func processTasks(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
}
java 解法, 执行用时: 166 ms, 内存消耗: 103.3 MB, 提交时间: 2023-09-26 20:18:51
class Solution {
public int processTasks(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
}
}
cpp 解法, 执行用时: 1172 ms, 内存消耗: 182.2 MB, 提交时间: 2023-09-26 20:18:39
class Solution {
public:
int processTasks(vector<vector<int>> &tasks) {
sort(tasks.begin(), tasks.end(), [](auto &a, auto &b) {
return a[1] < b[1];
});
vector<tuple<int, int, int>> 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 get<0>(a) < b;
});
d -= get<2>(st.back()) - s; // 去掉运行中的时间点
if (start <= r) // start 在区间 st[i] 内
d -= r - start + 1; // 去掉运行中的时间点
if (d <= 0) continue;
while (end - get<1>(st.back()) <= d) { // 剩余的 d 填充区间后缀
auto[l, r, _] = st.back();
d += r - l + 1; // 合并区间
st.pop_back();
}
st.emplace_back(end - d + 1, end, get<2>(st.back()) + d);
}
return get<2>(st.back());
}
};
python3 解法, 执行用时: 692 ms, 内存消耗: 72.8 MB, 提交时间: 2023-09-26 20:18:26
class Solution:
def processTasks(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]
python3 解法, 执行用时: 732 ms, 内存消耗: 71.3 MB, 提交时间: 2023-09-26 20:18:02
class Solution:
def processTasks(self, tasks) -> int:
tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵
res, q = 0, []
for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :
while q and q[0][0]+res < s :
if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除
else : res += min(q[0][1], s) - (q[0][0]+res)
heapq.heappush(q, [e-p+1-res, e+1])
return res