本文涉及知识点
C++堆(优先队列)
LeetCode1834. 单线程 CPU
给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
CPU 可以在完成一项任务后，立即开始执行一项新任务。
返回 CPU 处理任务的顺序。
示例 1：
输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
输出：[0,2,3,1]
解释：事件按下述流程运行：
- time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
- 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
- time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
- time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
- 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
- time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
- time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
- time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
- time = 10 ，CPU 完成任务 1 并进入空闲状态
示例 2：
输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出：[4,3,2,0,1]
解释：事件按下述流程运行： - time = 7 ，所有任务同时进入任务队列，可执行任务项 = {0,1,2,3,4}
- 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
- time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
- time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
- time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
- time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
- time = 40 ，CPU 完成任务 1 并进入空闲状态
提示：
tasks.length == n
1 <= n <= 105
1 <= enqueueTimei, processingTimei <= 109
堆(优先队列)
一，将tasks的下标indexs，按进入时间的顺序排序，进入时间相同，则处理时间短的在前面。
二，初始完成时间finish =-1。
三，将进入时间<=finish的任务放到小根堆中。堆元素包括：处理时间和下标。
四，如果小根堆为空，取第一个未执行的任务。如果没有未执行的任务，退出循环。
五，执行任务，并更新finish 为当前任务的完成时间。
代码
核心代码
class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
const int N = tasks.size();
vector<int> indexs(N);
iota(indexs.begin(), indexs.end(), 0);
sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {
if (tasks[i1] == tasks[i2]) { return i1 < i2; }
return tasks[i1] < tasks[i2];
});
priority_queue<pair<int, int>, vector< pair<int, int>>, greater<>> minHeap;
long long finish = -1;
vector<int> ret;
for (int i = 0; ;) {
while ((i < indexs.size()) && (tasks[indexs[i]][0] <= finish)) {
minHeap.emplace(tasks[indexs[i]][1], indexs[i]);
i++;
}
if (minHeap.empty()) {
if (i >= indexs.size()) { break; }//所有都已经处理
minHeap.emplace(tasks[indexs[i]][1], indexs[i]);
finish = tasks[indexs[i]][0];
i++;
}
finish += minHeap.top().first;
ret.emplace_back(minHeap.top().second);
minHeap.pop();
}
return ret;
}
};
单元测试
vector<vector<int>> tasks;
TEST_METHOD(TestMethod1)
{
tasks = { {7,1} };
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{0}, res);
}
TEST_METHOD(TestMethod2)
{
tasks = { {7,3},{9,2},{10,1} };
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{0,2,1}, res);
}
TEST_METHOD(TestMethod3)
{
tasks = { {7,2},{9,2},{10,1} };
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{0, 1,2}, res);
}
TEST_METHOD(TestMethod4)
{
tasks.assign(3, { 1'000'000'000,1'000'000'000 });
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{0, 1, 2}, res);
}
TEST_METHOD(TestMethod11)
{
tasks = { {1,2},{2,4},{3,2},{4,1} };
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{0, 2, 3, 1}, res);
}
TEST_METHOD(TestMethod12)
{
tasks = { {7,10},{7,12},{7,5},{7,4},{7,2} };
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{4, 3, 2, 0, 1}, res);
}
TEST_METHOD(TestMethod13)
{
tasks = { {19,13},{16,9},{21,10},{32,25},{37,4},{49,24},{2,15},{38,41},{37,34},{33,6},{45,4},{18,18},{46,39},{12,24} };
auto res = Solution().getOrder(tasks);
AssertEx(vector<int>{6, 1, 2, 9, 4, 10, 0, 11, 5, 13, 3, 8, 12, 7}, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
