题目描述
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.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example1:
Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
NOTE
- The number of tasks is in the range [1, 10000].
- The integer n is in the range [0, 100].
解题思路
- 首先要理解题意，相同任务之间需要有 n 的冷却期， 可以举一个例子
AAAABBBEEFFGG 3 我们发现任务A出现了4次，频率最高，于是我们在每个A中间加入三个空位，如下： A—A—A—A AB–AB–AB–A (加入B) ABE-ABE-AB–A (加入E) ABEFABE-ABF-A (加入F，每次尽可能填满或者是均匀填充) ABEFABEGABFGA (加入G)
- 我们都分成了(mx - 1)块，再加上最后面的字母，其中mx为最大出现次数。比如例子1中，A出现了4次，所以有A—模块出现了3次，再加上最后的A，每个模块的长度为4。所以最终的长度应为 (mx - 1) * (n + 1) + 1 （其中1为在整个任务列表中1个任务出现的次数最高）
- 我们可以求出来有几个任务，出现次数相等并且最高,最后 由 块数 * 每个块的任务数 + 后面需要补齐的任务数 即可得到结果
- 参考博客
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> cnt(26, 0);
for(auto& t : tasks){
cnt[t - 'A']++;
}
sort(cnt.begin(), cnt.end());
int i = 25, mx = cnt[25], len = tasks.size();
while(i >= 0 && cnt[i] == mx){
i--;
} // 最后需要增加 （25 - i） 的多余位置
return max(len, (mx - 1) * (n + 1) + (25 - i));
}
};
