Medium
我觉得，一个解法最要紧是能convince yourself. 很多lc高票答案看上去过于华丽，根本不好理解，无法使自己信服说ok I got it. 这样的解法还是不要了吧，宁愿去掌握那些看起来笨一点，但是Hell yeah I got it的那种解法，因为考到了你才真的能写出来，说出来思路，而不是抄了答案背了答案，让你说一下思路你根本是乱的。
讲解：https://www.youtube.com/watch?v=YCD_iYxyXoo
image.png
例如相同task之间至少要间隔n个interval，我们先计算出每个task出现的频率，找到出现频率最高的tasks. 比如这里我们知道task A出现的频率最高，频率为maxFreq = k. 我们就分k - 1个group，每个group里面有n + 1个slots. 为什么要分k - 1个不是k个呢，因为这k - 1个groups如果n + 1个slots不能用task填满的话需要用idle去填满，但最后一组我们可以不在尾部放idle. 所以最后一组比较特殊，所以我们才分成k - 1 groups + 1 last group.
image.png
这个题有一种特殊情况，会导致算出来的number of intervals < task.length. 这种情况为什么会发生呢，是因为我们按照 n + 1 slots计算的时候，可能并没把那些低频的task放进去，slots就不够了. 比如说上图中，我们前面3个group, 每个group有n + 1 = 3个slots. 我们按照高频到低频放，发现D, F, G这些低频的根本还没放完。 然而我们最后加the last group的时候只会加the highest frequency task， 这里就是A, 却不会特意去加上F,D,G这些低频任务，所以会导致我们算出来的number of intervals比任务总数还小，这个答案明显是invalid. 这时候比较容易看出来，我们不需要加任何idle interval就可以排tasks保证达到要求的cooling periods, 所以这种情况下答案就是task.length
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freqs = new int[26];
for (char c : tasks){
freqs[c - 'A']++;
}
Arrays.sort(freqs);
int maxFreq = freqs[25];
int maxCount = 0;
for (int freq : freqs){
if (freq == maxFreq){
maxCount++;
}
}
int ans = (maxFreq - 1) * ( n + 1) + count;
return Math.max(ans, tasks.length);
}
}
