网站交换链接的常见形式,徐州祥云平台,微信网站开发教程视频教程,网站动态图怎么做文章目录1. 题目2. 解题1. 题目
给你一个二维数组 tasks #xff0c;用于表示 n 项从 0 到 n - 1 编号的任务。 其中 tasks[i] [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列#xff0c;需要 pro…
文章目录1. 题目2. 解题1. 题目
给你一个二维数组 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 10^5
1 enqueueTimei, processingTimei 10^9https://leetcode-cn.com/contest/weekly-contest-237/problems/single-threaded-cpu/
2. 解题
先按时间排序任务将任务加入优先队列优先队列出列的时候更新当前时间然后将到时间了的需要执行的任务加入优先队列重复此步骤
typedef pairint,int pii;
struct cmp{bool operator()(pii a, pii b) const{ // 持续时间下标 piarif(a.first b.first) return a.second b.second;//下标小的优先return a.first b.first;//持续时间短的优先}
};class Solution {
public:vectorint getOrder(vectorvectorint tasks) {int n tasks.size(), k 0;vectorint ans(n);vectorint idx(n);iota(idx.begin(), idx.end(), 0);sort(idx.begin(), idx.end(),[](auto a, auto b){return tasks[a][0] tasks[b][0];//按开始时间排序});priority_queuepii,vectorpii,cmp q;// 存储 {持续时间下标}int t 0;for(int i 0; i n; ){while(i n tasks[idx[i]][0] t){ // 等待执行的任务加入队列q.push({tasks[idx[i]][1], idx[i]});i;}if(!q.empty()){ // 做任务优先级最高的先int delta q.top().first, id q.top().second;int start tasks[id][0]; // 任务开始时间q.pop();ans[k] id;t max(t, start);//当前时间t delta;// t 为干完活的时间}else // 队列为空时间移到下一个任务{t tasks[idx[i]][0];}}while(!q.empty()){int id q.top().second;q.pop();ans[k] id;}return ans;}
};576 ms 112.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
