{"id":706,"date":"2017-10-28T11:36:53","date_gmt":"2017-10-28T18:36:53","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=706"},"modified":"2018-04-19T08:30:49","modified_gmt":"2018-04-19T15:30:49","slug":"leetcode-621-task-scheduler","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-621-task-scheduler\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 621. Task Scheduler"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 621. Task Scheduler - \u5237\u9898\u627e\u5de5\u4f5c EP98\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/YCD_iYxyXoo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u7528\u5b57\u6bcd\u8868\u793a\u7684\u4efb\u52a1\uff0c\u6267\u884c\u6bcf\u4e2a\u4efb\u52a1\u9700\u8981\u5355\u4f4d\u65f6\u95f4\u7684CPU\u3002\u5bf9\u4e8e\u76f8\u540c\u7684\u4efb\u52a1\uff0cCPU\u9700\u8981n\u4e2a\u5355\u4f4d\u65f6\u95f4\u7684\u51b7\u5374\u65f6\u95f4\uff0c\u671f\u95f4\u53ef\u4ee5\u6267\u884c\u5176\u4ed6\u4e0d\u76f8\u540c\u7684\u4efb\u52a1\u3002\u95ee\u6700\u5c11\u591a\u5c11\u65f6\u95f4\u53ef\u4ee5\u5b8c\u6210\u6240\u6709\u4efb\u52a1\u3002<\/p>\n<p>Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.<\/p>\n<p>However, there is a non-negative cooling interval\u00a0<b>n<\/b>\u00a0that means between two\u00a0<b>same tasks<\/b>, there must be at least n intervals that CPU are doing different tasks or just be idle.<\/p>\n<p>You need to return the\u00a0<b>least<\/b>\u00a0number of intervals the CPU will take to finish all the given tasks.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">Input: tasks = [\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], n = 2\r\nOutput: 8\r\nExplanation: A -&gt; B -&gt; idle -&gt; A -&gt; B -&gt; idle -&gt; A -&gt; B.\r\n<\/pre>\n<p><strong>N<\/strong><b>ote:<\/b><\/p>\n<ol>\n<li>The number of tasks is in the range [1, 10000].<\/li>\n<li>The integer n is in the range [0, 100].<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>Counting<\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 56 ms\r\nclass Solution {\r\npublic:\r\n    int leastInterval(vector&lt;char&gt;&amp; tasks, int n) {\r\n        vector&lt;int&gt; count(26, 0);        \r\n        for (const char task : tasks) \r\n            ++count[task - 'A'];\r\n        const int max_count = *max_element(count.begin(), count.end());\r\n        size_t ans = (max_count - 1) * (n + 1);\r\n        ans += count_if(count.begin(), count.end(),\r\n                        [max_count](int c){ return c == max_count; });\r\n        return max(tasks.size(), ans);\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u7528\u5b57\u6bcd\u8868\u793a\u7684\u4efb\u52a1\uff0c\u6267\u884c\u6bcf\u4e2a\u4efb\u52a1\u9700\u8981\u5355\u4f4d\u65f6\u95f4\u7684CPU\u3002\u5bf9\u4e8e\u76f8\u540c\u7684\u4efb\u52a1\uff0cCPU\u9700\u8981n\u4e2a\u5355\u4f4d\u65f6\u95f4\u7684\u51b7\u5374\u65f6\u95f4\uff0c\u671f\u95f4\u53ef\u4ee5\u6267\u884c\u5176\u4ed6\u4e0d\u76f8\u540c\u7684\u4efb\u52a1\u3002\u95ee\u6700\u5c11\u591a\u5c11\u65f6\u95f4\u53ef\u4ee5\u5b8c\u6210\u6240\u6709\u4efb\u52a1\u3002 Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51,164],"tags":[146,147],"class_list":["post-706","post","type-post","status-publish","format-standard","hentry","category-greedy","category-medium","tag-scheduling","tag-task","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/706","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=706"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/706\/revisions"}],"predecessor-version":[{"id":2570,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/706\/revisions\/2570"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=706"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=706"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=706"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}