【C++堆(优先队列)】1882. 使用服务器处理任务|1979

本文涉及知识点

C++堆(优先队列)

LeetCode1882. 使用服务器处理任务

给你两个 下标从 0 开始 的整数数组 servers 和 tasks ，长度分别为 n​​​​​​ 和 m​​​​​​ 。servers[i] 是第 i​​​​​​​​​​ 台服务器的 权重 ，而 tasks[j] 是处理第 j​​​​​​ 项任务 所需要的时间（单位：秒）。
你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时，你需要为它分配一台 权重最小 的空闲服务器。如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器。如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。
如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 尽可能早 地处理剩余任务。 如果有多项任务等待分配，则按照 下标递增 的顺序完成分配。
如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。
构建长度为 m 的答案数组 ans ，其中 ans[j] 是第 j 项任务分配的服务器的下标。
返回答案数组 ans​​​​ 。
示例 1：
输入：servers = [3,3,2], tasks = [1,2,3,2,1,2]
输出：[2,2,0,2,1,2]
解释：事件按时间顺序如下：

• 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。
• 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。
• 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。
• 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。
• 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。
• 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。
  示例 2：

输入：servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
输出：[1,4,1,4,1,3,2]
解释：事件按时间顺序如下：

• 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。
• 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。
• 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。
• 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。
• 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。
• 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。
• 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。
  提示：
  servers.length == n
  tasks.length == m
  1 <= n, m <= 2 * 10⁵
  1 <= servers[i], tasks[j] <= 2 * 10⁵

堆优先队列

我们用小根堆记录空闲的服务器信息：权重 下标。
我们用小根堆记录忙录的服务器：完成时间 权重 下标。
依次处理第j项任务：
将结束时间<= j 运行服务器，移到空闲服务器。。
如果没有空闲服务器，运行第一个运行服务器。开始时间 运行服务器堆顶服务器的结束时间。
$$\{\begin{array}{llc}在空闲的服务器的堆顶服务器运行，开始时间j，移除堆顶元素。& & 有空闲服务器\\ 忙碌的服务器的堆顶服务器运行，开始时间：堆顶服务器的结束时间，移除堆顶元素& & ohter\end{array}$$
将{开始时间+task[j],server[服务器下标],服务器下标}加到运行堆。

代码

核心代码

class Solution {public:vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {priority_queue<pair<int, int>,vector<pair<int, int>>,greater<>> heapIdle;priority_queue<tuple<int, int,int>, vector<tuple<int, int,int>>, greater<>> heapRun;for (int i = 0; i < servers.size(); i++) {heapIdle.emplace(servers[i], i);}vector<int> ret;for (int j = 0; j < tasks.size(); j++) {while (heapRun.size() && (get<0>(heapRun.top()) <= j)) {heapIdle.emplace(get<1>(heapRun.top()), get<2>(heapRun.top()));heapRun.pop();}int time = 0, index = -1;if (heapIdle.size()) {time = j;index = get<1>(heapIdle.top());heapIdle.pop();}else {time = get<0>(heapRun.top());index = get<2>(heapRun.top());heapRun.pop();}ret.emplace_back(index);heapRun.emplace(time + tasks[j], servers[index], index);}return ret;}};

单元测试

	vector<int> servers,  tasks;TEST_METHOD(TestMethod11){servers = { 3, 3, 2 }, tasks = { 1, 2, 3, 2, 1, 2 };auto res = Solution().assignTasks(servers, tasks);AssertEx(vector<int>{2, 2, 0, 2, 1, 2}, res);}TEST_METHOD(TestMethod12){servers = { 5,1,4,3,2 }, tasks = { 2,1,2,4,5,2,1 };auto res = Solution().assignTasks(servers, tasks);AssertEx(vector<int>{1, 4, 1, 4, 1, 3, 2}, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。