• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode 621 任务调度器

开发技术 开发技术 3小时前 1次浏览

放桶子的思想,首先遍历数组,记录出现次数最任务的次数以及并列的个数,设为m和x,由于存在冷却时间,单单执行最多次数的任务所需要的时间就是(m-1)*(n+1)+1,这就相当于放了m-1个桶,最后一个1是执行最后一个该任务的耗时,再加上需执行次数同样多的任务,则执行这些任务最少的时间变为(m-1)*(n+1)+x和任务个数的最大值,前一个数是在桶子中的冷却时间并未被填满的情况,第二个则是冷却时间全部被填满,该情况下若是有其他的任务待执行,可以直接在每个桶子后面执行,这样的结果并不会造成额外的空置时间。这种情况下,总的执行时间就是任务的数量。综上,计算出m,x的数据,再比较(m-1)*(n+1)+x和任务个数中最大值,就得到了最后的答案,改题解链接为:https://leetcode-cn.com/problems/task-scheduler/solution/tong-zi-by-popopop/。贴代码

 1 class Solution {
 2 public:
 3     int leastInterval(vector<char>& tasks, int n) 
 4     {
 5         unordered_map<char,int> hash;
 6         for(auto ch:tasks)
 7         {
 8             hash[ch]++;
 9         }
10         int m = 0;
11         int x = 0;
12         for(auto pair:hash)
13         {
14             if(pair.second>m)
15             {
16                 m = pair.second;
17                 x = 1;
18             }
19             else if(pair.second == m)
20             x++;
21         }
22         int num1 = (m-1)*(n+1)+x;
23         int num2 = tasks.size(); 
24         return max(num1,num2);                        
25     }
26 };

 


程序员灯塔
转载请注明原文链接:leetcode 621 任务调度器
喜欢 (0)