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.
Example 1:
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].
解法一
https://leetcode.com/problems/task-scheduler/discuss/104496/concise-java-solution-on-time-o26-space
by fatalme
这道题让我们安排CPU的任务，规定在两个相同任务之间至少隔n个时间点。说实话，刚开始博主并没有完全理解题目的意思，后来看了大神们的解法才悟出个道理来。下面这种解法参考了大神fatalme的帖子，由于题目中规定了两个相同任务之间至少隔n个时间点，那么我们首先应该处理的出现次数最多的那个任务，先确定好这些高频任务，然后再来安排那些低频任务。如果任务F的出现频率最高，为k次，那么我们用n个空位将每两个F分隔开，然后我们按顺序加入其他低频的任务，来看一个例子：
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)
再来看一个例子：
ACCCEEE 2
我们发现任务C和E都出现了三次，那么我们就将CE看作一个整体，在中间加入一个位置即可：
CE-CE-CE
CEACE-CE (加入A)
注意最后面那个idle不能省略，不然就不满足相同两个任务之间要隔2个时间点了。
这道题好在没有让我们输出任务安排结果，而只是问所需的时间总长，那么我们就想个方法来快速计算出所需时间总长即可。我们仔细观察上面两个例子可以发现，都分成了(mx - 1)块，再加上最后面的字母，其中mx为最大出现次数。比如例子1中，A出现了4次，所以有A---模块出现了3次，再加上最后的A，每个模块的长度为4。例子2中，CE-出现了2次，再加上最后的CE，每个模块长度为3。我们可以发现，模块的次数为任务最大次数减1，模块的长度为n+1，最后加上的字母个数为出现次数最多的任务，可能有多个并列。这样三个部分都搞清楚了，写起来就不难了，我们统计每个大写字母出现的次数，然后排序，这样出现次数最多的字母就到了末尾，然后我们向前遍历，找出出现次数一样多的任务个数，就可以迅速求出总时间长了，下面这段代码可能最不好理解的可能就是最后一句了，那么我们特别来讲解一下。先看括号中的第二部分，前面分析说了mx是出现的最大次数，mx-1是可以分为的块数，n+1是每块中的个数，而后面的 25-i 是还需要补全的个数，用之前的例子来说明：
AAAABBBEEFFGG 3
A出现了4次，最多，mx=4，那么可以分为mx-1=3块，如下：
A---A---A---
每块有n+1=4个，最后还要加上末尾的一个A，也就是25-24=1个任务，最终结果为13：
ABEFABEGABFGA
再来看另一个例子：
ACCCEEE 2
C和E都出现了3次，最多，mx=3，那么可以分为mx-1=2块，如下：
CE-CE-
每块有n+1=3个，最后还要加上末尾的一个CE，也就是25-23=2个任务，最终结果为8：
CEACE-CE
好，那么此时你可能会有疑问，为啥还要跟原任务个数len相比，取较大值呢？我们再来看一个例子：
AAABBB 0
A和B都出现了3次，最多，mx=3，那么可以分为mx-1=2块，如下：
ABAB
每块有n+1=1个？你会发现有问题，这里明明每块有两个啊，为啥这里算出来n+1=1呢，因为给的n=0，这有没有矛盾呢，没有！因为n表示相同的任务间需要间隔的个数，那么既然这里为0了，说明相同的任务可以放在一起，这里就没有任何限制了，我们只需要执行完所有的任务就可以了，所以我们最终的返回结果一定不能小于任务的总个数len的，这就是要对比取较大值的原因了。
参见代码如下：
// (c[25] - 1) * (n + 1) + 25 - i is frame size
// when inserting chars, the frame might be "burst", then tasks.length takes precedence
// when 25 - i > n, the frame is already full at construction, the following is still valid.
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] c = new int[26];
for(char t : tasks){
c[t - ‘A‘]++;
}
Arrays.sort(c);
int i = 25;
while(i >= 0 && c[i] == c[25]) i--;
return Math.max(tasks.length, (c[25] - 1) * (n + 1) + 25 - i);
}
}
解法二
下面这种解法是根据大神jinzhou的帖子，优点是代码更容易读懂，而且变量命名很reasonable，前半部分都是一样的，求出最多的次数mx，还有同时出现mx次的不同任务的个数mxCnt。这个解法的思想是先算出所有空出来的位置，然后计算出所有需要填入的task的个数，如果超出了空位的个数，就需要最后再补上相应的个数。注意这里如果有多个任务出现次数相同，那么将其整体放一起，就像上面的第二个例子中的CE一样，那么此时每个part中的空位个数就是n - (mxCnt - 1)，那么空位的总数就是part的总数乘以每个part中空位的个数了，那么我们此时除去已经放入part中的，还剩下的task的个数就是task的总个数减去mx * mxCnt，然后此时和之前求出的空位数相比较，如果空位数要大于剩余的task数，那么则说明还需补充多余的空位，否则就直接返回task的总数即可，参见代码如下：
The key is to find out how many idles do we need.
Let‘s first look at how to arrange them. it‘s not hard to figure out that we can do a "greedy arrangement": always arrange task with most frequency first.
E.g. we have following tasks : 3 A, 2 B, 1 C. and we have n = 2. According to what we have above, we should first arrange A, and then B and C. Imagine there are "slots" and we need to arrange tasks by putting them into "slots". Then A should be put into slot 0, 3, 6 since we need to have at least n = 2 other tasks between two A. After A put into slots, it looks like this:
A ? ? A ? ? A
"?" is "empty" slots.
Now we can use the same way to arrange B and C. The finished schedule should look like this:
A B C A B # A
"#" is idle
Now we have a way to arrange tasks. But the problem only asks for number of CPU intervals, so we don‘t need actually arrange them. Instead we only need to get the total idles we need and the answer to problem is just number of idles + number of tasks.
Same example: 3 A, 2 B, 1 C, n = 2. After arranging A, we have:
A ? ? A ? ? A
We can see that A separated slots into (count(A) - 1) = 2 parts, each part has length n. With the fact that A is the task with most frequency, it should need more idles than any other tasks. In this case if we can get how many idles we need to arrange A, we will also get number of idles needed to arrange all tasks. Calculating this is not hard, we first get number of parts separated by A: partCount = count(A) - 1; then we can know number of empty slots: emptySlots = partCount * n; we can also get how many tasks we have to put into those slots: availableTasks = tasks.length - count(A). Now if we have emptySlots > availableTasks which means we have not enough tasks available to fill all empty slots, we must fill them with idles. Thus we have idles = max(0, emptySlots - availableTasks);
Almost done. One special case: what if there are more than one task with most frequency? OK, let‘s look at another example: 3 A 3 B 2 C 1 D, n = 3
Similarly we arrange A first:
A ? ? ? A ? ? ? A
Now it‘s time to arrange B, we find that we have to arrange B like this:
A B ? ? A B ? ? A B
we need to put every B right after each A. Let‘s look at this in another way, think of sequence "A B" as a special task "X", then we got:
X ? ? X ? ? X
Comparing to what we have after arranging A:
A ? ? ? A ? ? ? A
The only changes are length of each parts (from 3 to 2) and available tasks. By this we can get more general equations:
partCount = count(A) - 1
emptySlots = partCount * (n - (count of tasks with most frequency - 1))
availableTasks = tasks.length - count(A) * count of tasks with most frenquency
idles = max(0, emptySlots - availableTasks)
result = tasks.length + idles
What if we have more than n tasks with most frequency and we got emptySlot negative? Like 3A, 3B, 3C, 3D, 3E, n = 2. In this case seems like we can‘t put all B C S inside slots since we only have n = 2.
Well partCount is actually the "minimum" length of each part required for arranging A. You can always make the length of part longer.
E.g. 3A, 3B, 3C, 3D, 2E, n = 2.
You can always first arrange A, B, C, D as:
A B C D | A B C D | A B C D
in this case you have already met the "minimum" length requirement for each part (n = 2), you can always put more tasks in each part if you like:
e.g.
A B C D E | A B C D E | A B C D
emptySlots < 0 means you have already got enough tasks to fill in each part to make arranged tasks valid. But as I said you can always put more tasks in each part once you met the "minimum" requirement.
To get count(A) and count of tasks with most frequency, we need to go through inputs and calculate counts for each distinct char. This is O(n) time and O(26) space since we only handle upper case letters.
All other operations are O(1) time O(1) space which give us total time complexity of O(n) and space O(1)
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] counter = new int[26];
int max = 0;
int maxCount = 0;
for(char task : tasks) {
counter[task - ‘A‘]++;
if(max == counter[task - ‘A‘]) {
maxCount++;
}
else if(max < counter[task - ‘A‘]) {
max = counter[task - ‘A‘];
maxCount = 1;
}
}
int partCount = max - 1;
int partLength = n - (maxCount - 1);
int emptySlots = partCount * partLength;
int availableTasks = tasks.length - max * maxCount;
int idles = Math.max(0, emptySlots - availableTasks);
return tasks.length + idles;
}
}