本文主要是介绍**Leetcode 621. Task Scheduler，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/task-scheduler/description/
不知道为啥模拟写残了，
然后思路可以参考这里https://www.cnblogs.com/grandyang/p/7098764.html
这道题让我们安排CPU的任务，规定在两个相同任务之间至少隔n个时间点。说实话，刚开始博主并没有完全理解题目的意思，后来看了大神们的解法才悟出个道理来。下面这种解法参考了大神fatalme的帖子，由于题目中规定了两个相同任务之间至少隔n个时间点，那么我们首先应该处理的出现次数最多的那个任务，先确定好这些高频任务，然后再来安排那些低频任务。如果任务F的出现频率最高，为k次，那么我们用n个空位将每两个F分隔开，然后我们按顺序加入其他低频的任务，来看一个例子：AAAABBBEEFFGG 3我们发现任务A出现了4次，频率最高，于是我们在每个A中间加入三个空位，如下：A---A---A---AAB--AB--AB--A (加入B)ABE-ABE-AB--A (加入E)ABEFABE-ABF-A (加入F，每次尽可能填满或者是均匀填充)ABEFABEGABFGA (加入G)再来看一个例子：ACCCEEE 2我们发现任务C和E都出现了三次，那么我们就将CE看作一个整体，在中间加入一个位置即可：CE-CE-CECEACE-CE (加入A)注意最后面那个idle不能省略，不然就不满足相同两个任务之间要隔2个时间点了。这道题好在没有让我们输出任务安排结果，而只是问所需的时间总长，那么我们就想个方法来快速计算出所需时间总长即可。我们仔细观察上面两个例子可以发现，都分成了(mx - 1)块，再加上最后面的字母，其中mx为最大出现次数。比如例子1中，A出现了4次，所以有A---模块出现了3次，再加上最后的A，每个模块的长度为4。例子2中，CE-出现了2次，再加上最后的CE，每个模块长度为3。我们可以发现，模块的次数为任务最大次数减1，模块的长度为n+1，最后加上的字母个数为出现次数最多的任务，可能有多个并列。这样三个部分都搞清楚了，写起来就不难了，我们统计每个大写字母出现的次数，然后排序，这样出现次数最多的字母就到了末尾，然后我们向前遍历，找出出现次数一样多的任务个数，就可以迅速求出总时间长了bool cmp(const int a, const int b) {return a > b;
}
class Solution {
public:int leastInterval(vector<char>& tasks, int n) {int counter[26];memset(counter, 0, sizeof(counter));for (int i = 0; i < tasks.size(); i++) {counter[ tasks[i] - 'A' ] ++ ;}sort(counter, counter+26, cmp);int ret = 0, done = 0;int mx = counter[0];int i = 0;while (i < 26 && counter[i] == mx) i ++;return max((int)tasks.size(), (mx-1) * (n+1) + i);// while ( done < tasks.size() ) {// int cur = 0;// bool first = true;// for (int i = 0; i < 26; i++) {// if (counter[i] != 0) {// if (first) pos = i, first = false;// cur ++;// counter[i] --;// done++;// }// if (cur >= n+1) break;// }// if (cur < n+1 && done < tasks.size() && ( last == pos|| last == -1)) ret += n + 1 - cur;// ret += cur;// last = pos;// }// return ret;}
};这篇关于**Leetcode 621. Task Scheduler的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
