{"id":8376,"date":"2021-04-18T10:17:53","date_gmt":"2021-04-18T17:17:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8376"},"modified":"2021-04-18T10:18:12","modified_gmt":"2021-04-18T17:18:12","slug":"leetcode-1834-single-threaded-cpu","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1834-single-threaded-cpu\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1834. Single-Threaded CPU"},"content":{"rendered":"\n<p>You are given&nbsp;<code>n<\/code>\u200b\u200b\u200b\u200b\u200b\u200b tasks labeled from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n - 1<\/code>&nbsp;represented by a 2D integer array&nbsp;<code>tasks<\/code>, where&nbsp;<code>tasks[i] = [enqueueTime<sub>i<\/sub>, processingTime<sub>i<\/sub>]<\/code>&nbsp;means that the&nbsp;<code>i<sup>\u200b\u200b\u200b\u200b\u200b\u200bth<\/sup><\/code>\u200b\u200b\u200b\u200b task will be available to process at&nbsp;<code>enqueueTime<sub>i<\/sub><\/code>&nbsp;and will take&nbsp;<code>processingTime<sub>i<\/sub><\/code>to finish processing.<\/p>\n\n\n\n<p>You have a single-threaded CPU that can process&nbsp;<strong>at most one<\/strong>&nbsp;task at a time and will act in the following way:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If the CPU is idle and there are no available tasks to process, the CPU remains idle.<\/li><li>If the CPU is idle and there are available tasks, the CPU will choose the one with the&nbsp;<strong>shortest processing time<\/strong>. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.<\/li><li>Once a task is started, the CPU will&nbsp;<strong>process the entire task<\/strong>&nbsp;without stopping.<\/li><li>The CPU can finish a task then start a new one instantly.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the order in which the CPU will process the tasks.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> tasks = [[1,2],[2,4],[3,2],[4,1]]\n<strong>Output:<\/strong> [0,2,3,1]\n<strong>Explanation: <\/strong>The events go as follows: \n- At time = 1, task 0 is available to process. Available tasks = {0}.\n- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.\n- At time = 2, task 1 is available to process. Available tasks = {1}.\n- At time = 3, task 2 is available to process. Available tasks = {1, 2}.\n- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.\n- At time = 4, task 3 is available to process. Available tasks = {1, 3}.\n- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.\n- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.\n- At time = 10, the CPU finishes task 1 and becomes idle.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]\n<strong>Output:<\/strong> [4,3,2,0,1]\n<strong>Explanation<\/strong><strong>: <\/strong>The events go as follows:\n- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.\n- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.\n- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.\n- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.\n- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.\n- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.\n- At time = 40, the CPU finishes task 1 and becomes idle.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>tasks.length == n<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= enqueueTime<sub>i<\/sub>, processingTime<sub>i<\/sub>&nbsp;&lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulation w\/ Sort + PQ<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> getOrder(vector<vector<int>>& tasks) {\n    const int n = tasks.size();\n    for (int i = 0; i < n; ++i)\n      tasks[i].push_back(i);\n    sort(begin(tasks), end(tasks)); \/\/ sort by enqueue_time;    \n    \n    vector<int> ans;\n    priority_queue<pair<int, int>> q; \/\/ {-processing_time, -index}\n    int i = 0;\n    long t = 0;    \n    while (ans.size() != n) {\n      \/\/ Advance to next enqueue time if q is empty.\n      if (i < n &#038;&#038; q.empty() &#038;&#038; tasks[i][0] > t)\n        t = tasks[i][0];\n      \/\/ Enqueue all available tasks.\n      while (i < n &#038;&#038; tasks[i][0] <= t) {\n        q.emplace(-tasks[i][1], -tasks[i][2]);\n        ++i;\n      }\n      \/\/ Extra the top one.\n      t -= q.top().first;\n      ans.push_back(-q.top().second);\n      q.pop();      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given&nbsp;n\u200b\u200b\u200b\u200b\u200b\u200b tasks labeled from&nbsp;0&nbsp;to&nbsp;n &#8211; 1&nbsp;represented by a 2D integer array&nbsp;tasks, where&nbsp;tasks[i] = [enqueueTimei, processingTimei]&nbsp;means that the&nbsp;i\u200b\u200b\u200b\u200b\u200b\u200bth\u200b\u200b\u200b\u200b task will be available to process&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,708,72,179,23],"class_list":["post-8376","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-min-heap","tag-priority-queue","tag-simulation","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8376","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8376"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8376\/revisions"}],"predecessor-version":[{"id":8378,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8376\/revisions\/8378"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8376"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8376"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8376"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}