域名备案平台,seo网络营销招聘,中国建设银行官方网站e路航下载,代理赚钱本文涉及知识点
C堆(优先队列)
LeetCode1882. 使用服务器处理任务
给你两个 下标从 0 开始 的整数数组 servers 和 tasks #xff0c;长度分别为 n 和 m 。servers[i] 是第 i 台服务器的 权重 #xff0c;而 tasks[j] 是处理…本文涉及知识点
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 * 105 1 servers[i], tasks[j] 2 * 105
堆优先队列
我们用小根堆记录空闲的服务器信息权重 下标。 我们用小根堆记录忙录的服务器完成时间 权重 下标。 依次处理第j项任务 将结束时间 j 运行服务器移到空闲服务器。。 如果没有空闲服务器运行第一个运行服务器。开始时间 运行服务器堆顶服务器的结束时间。 { 在空闲的服务器的堆顶服务器运行开始时间 j 移除堆顶元素。 有空闲服务器 忙碌的服务器的堆顶服务器运行开始时间堆顶服务器的结束时间移除堆顶元素 o h t e r \begin{cases} 在空闲的服务器的堆顶服务器运行开始时间j 移除堆顶元素。 有空闲服务器 \\ 忙碌的服务器的堆顶服务器运行开始时间堆顶服务器的结束时间 移除堆顶元素 ohter \\ \end{cases} {在空闲的服务器的堆顶服务器运行开始时间j移除堆顶元素。忙碌的服务器的堆顶服务器运行开始时间堆顶服务器的结束时间移除堆顶元素有空闲服务器ohter 将{开始时间task[j],server[服务器下标],服务器下标}加到运行堆。
代码
核心代码
class Solution {public:vectorint assignTasks(vectorint servers, vectorint tasks) {priority_queuepairint, int,vectorpairint, int,greater heapIdle;priority_queuetupleint, int,int, vectortupleint, int,int, greater heapRun;for (int i 0; i servers.size(); i) {heapIdle.emplace(servers[i], i);}vectorint ret;for (int j 0; j tasks.size(); j) {while (heapRun.size() (get0(heapRun.top()) j)) {heapIdle.emplace(get1(heapRun.top()), get2(heapRun.top()));heapRun.pop();}int time 0, index -1;if (heapIdle.size()) {time j;index get1(heapIdle.top());heapIdle.pop();}else {time get0(heapRun.top());index get2(heapRun.top());heapRun.pop();}ret.emplace_back(index);heapRun.emplace(time tasks[j], servers[index], index);}return ret;}};单元测试 vectorint servers, tasks;TEST_METHOD(TestMethod11){servers { 3, 3, 2 }, tasks { 1, 2, 3, 2, 1, 2 };auto res Solution().assignTasks(servers, tasks);AssertEx(vectorint{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(vectorint{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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
