一、步骤分析
① 将当前时间戳时刻完成的事件出队,更新时间戳
② 将当前时间戳时刻应该入队的事件入队
③ 注意可能存在事件完成出队后时间戳小于入队要求时间戳的情况,这种情况需要特判,将时间戳直接改变成待入队事件发生的时间,然后按照循环逻辑继续进行
二、lc1834-单线程CPU
① 将已经到达任务队列中取出处理时间最短的,更新时间戳
② 将当前时间戳已经到达的任务全部入队
③ 如果当前等待队列中没有任务,且时间戳小于还未到达任务的最小到达时间,即如果时间戳小于待入队任务中最小的到达时间时,就需要将时间戳直接置为最小的到达时间,否则时间戳就会卡住
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
typedef long long LL;
class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
auto cmp = [&](PII a, PII b)
{
if (a.x != b.x) return a.x >= b.x; // 优先按照到达时间排序
int i = a.y, j = b.y;
return tasks[i][1] >= tasks[j][1]; // 到达时间相同的按照任务执行时间递增排序
};
priority_queue<PII, vector<PII>, decltype(cmp)> q(cmp); // <到达时间, 序号>
priority_queue<PII, vector<PII>, greater<PII>> work; // <持续时间, 序号>
for (int i = 0; i < tasks.size(); i ++) q.push({tasks[i][0], i}); // 进入时间,序号
vector<int> ans;
LL cur = q.top().x;
while (q.size() > 0 || work.size())
{
// 将cpu中执行结束的任务删除
if (work.size())
{
cur = cur + work.top().x; // 当前任务的结束时间
ans.push_back(work.top().y);
work.pop();
}
// while (work.size() && work.front() <= cur) work.pop();
// 将新的任务加进任务队列
while (q.size() && q.top().x <= cur)
{
work.push({tasks[q.top().y][1], q.top().y}); // 入队<持续时间, 序号>
q.pop();
}
// 如果当前时间戳小于要待入队的第一个任务,则要将时间戳更新为待入队的最早的时间
if (q.size() && cur < q.top().x && !work.size()) cur = q.top().x;
}
return ans;
}
};
三、lc6306-过桥的时间
四个堆分别表示左右侧工人工作状态、左右侧桥边等待的工人
① 将左右侧当前时间戳工作结束的工人加到桥边等待队列中
② 右侧桥边等待工人优先过桥(效率越低越先过),然后左侧工人在右侧还有箱子的情况下过桥,将过桥的时间直接算进时间戳,然后将工人和工人的结束时间加进左右侧工作队列
③ 如果没有工人过桥,那么说明所有工人都在工作状态,如果不更新时间戳就会卡住,这个时候需要将时间戳变成左右工作队列中工人最先结束的时间,然后就有工人工作结束,继续循环
时间戳卡住的根本原因是工人完成任务后过桥的时间小于当前时间戳
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
class Solution {
public:
int findCrossingTime(int n, int k, vector<vector<int>>& time) {
auto cmp = [&](int a, int b) // 等待队列中工人效率判断
{
int sa = time[a][0] + time[a][2];
int sb = time[b][0] + time[b][2];
return sa != sb ? sa < sb : a < b;
};
priority_queue<int, vector<int>, decltype(cmp)> wl(cmp), wr(cmp); // 存放左右两侧桥边等待的工人
priority_queue<PII, vector<PII>, greater<PII>> ql, qr; // 存放左右两侧工人搬箱子状态
int cur = 0;
for (int i = 0; i < k; i ++) wl.push(i); // 初始时所有工人都在左侧等待过桥
while (n > 0 || qr.size() > 0 || wr.size() > 0) // 只有当还剩余箱子或右侧还有工人没回来时才继续
{
// 先处理工作状态转化为等待状态
while (qr.size() && qr.top().x <= cur) // 将当前时刻右侧工作结束的工人放到右边等待队列中
{
wr.push(qr.top().y);
qr.pop();
}
while (ql.size() && ql.top().x <= cur) // 将当前时刻左侧工作结束的工人放到左边等待队列中
{
wl.push(ql.top().y);
ql.pop();
}
// 再将等待状态过桥,转化为工作状态
if (wr.size()) // 右侧等待的工人优先过桥
{
int t = wr.top(); wr.pop();
cur += time[t][2]; // 过桥耗时
ql.push({cur + time[t][3], t}); // 过桥后将箱子放下的完成时间
}
else if (wl.size() && n) // 左侧有工人要过去的前提是右侧还有没搬过来的箱子
{
int t = wl.top(); wl.pop();
cur += time[t][0];
qr.push({cur + time[t][1], t}); // 过桥后将箱子搬起来的结束时间
n --; // 箱子数量-1
}
else // 左右两侧都没有工人要过桥,那么cur要向后移动到左右两侧工作的工人最先结束的时刻
{
int over = 1e9;
if (ql.size()) over = min(over, ql.top().x);
if (qr.size()) over = min(over, qr.top().x);
cur = over; // 将时间更新为两侧最早一个工人结束的时刻
}
}
return cur;
}
};