C++刷LeetCode（1834. 单线程 CPU***）【模拟】【小顶堆】

糖逗

题目描述：

1. 给你一个二维数组 tasks ，用于表示 n​​​​​​ 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i​​​​​​​​​​ 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
   
2. 
   
3. 现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
   
4. 
   
5. 如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
   
6. 如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
   
7. 一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
   
8. CPU 可以在完成一项任务后，立即开始执行一项新任务。
   
9. 返回 CPU 处理任务的顺序。
   
10. 
    
11.  
    
12. 
    
13. 示例 1：
    
14. 
    
15. 输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
    
16. 输出：[0,2,3,1]
    
17. 解释：事件按下述流程运行：
    
18. - time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
    
19. - 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
    
20. - time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
    
21. - time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
    
22. - 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
    
23. - time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
    
24. - time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
    
25. - time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
    
26. - time = 10 ，CPU 完成任务 1 并进入空闲状态
    
27. 示例 2：
    
28. 
    
29. 输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
    
30. 输出：[4,3,2,0,1]
    
31. 解释：事件按下述流程运行：
    
32. - time = 7 ，所有任务同时进入任务队列，可执行任务项  = {0,1,2,3,4}
    
33. - 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
    
34. - time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
    
35. - time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
    
36. - time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
    
37. - time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
    
38. - time = 40 ，CPU 完成任务 1 并进入空闲状态
    
39.  
    
40. 
    
41. 提示：
    
42. 
    
43. tasks.length == n
    
44. 1 <= n <= 105
    
45. 1 <= enqueueTimei, processingTimei <= 109
    
46. 
    
47. 来源：力扣（LeetCode）
    
48. 链接：https://leetcode-cn.com/problems/single-threaded-cpu
    
49. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     struct cmp{
   
4.         bool operator() (const vector<int> &a, const vector<int> &b) {
   
5.             if(a[1] == b[1]) return a[2] > b[2];   
   
6.             return a[1] > b[1];   
   
7.         }
   
8.     };
   
9.     vector<int> getOrder(vector<vector<int>>& tasks) {
   
10.         //模拟
    
11.         int len = tasks.size();
    
12.         for(int i = 0; i < len; i++){
    
13.             tasks[i].push_back(i);
    
14.         }
    
15.         sort(tasks.begin(), tasks.end(), [&](vector<int>&a, vector<int>&b){
    
16.             return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
    
17.         });
    
18.         vector<int>res;
    
19.         int timestamp = 0;
    
20.         priority_queue<vector<int>, vector<vector<int> >, cmp>store;
    
21.         for(int i = 0; i < len;){
    
22.             if(store.empty()){
    
23.                 timestamp = max(timestamp, tasks[i][0]);
    
24.             }
    
25.             while(i < len && tasks[i][0] <= timestamp){
    
26.                 store.push(tasks[i]);
    
27.                 i++;
    
28.             }
    
29.             res.push_back(store.top()[2]);
    
30.             timestamp += store.top()[1];
    
31.             store.pop();
    
32.         }
    
33.         while(!store.empty()) {
    
34.             res.push_back(store.top()[2]);
    
35.             store.pop();
    
36.         }
    
37.         return res;
    
38.     }
    
39. };
    
40. 
    

复制代码