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: 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].
贪心算法对我来说真的实在是难，像这种题目基本就无从下手。不过算法真的很巧妙。
任务优先处理最频繁的：这点可以用一个简单的例子说明：["A","B","B"] n = 2
先处理B->A->idel->B.res=4 先处理A->B->idle->idle->B res=5
最频繁任务决定了整个处理序列的"关键点"。
假设任务列表为["A","A","A","B","B","C"] n = 2
则A是最频繁任务，A决定了序列的关键点：
A _ _ A _ _ A
_表示为idle，然后把剩下的任务填入_即可。
A B C A B _ A.所以结果实际上就是tasks任务长度加上idle的数量。
算法的难点就在于此：如果填满_并且超出了呢？其实这样不会造成额外的idle：
比如：["A","A","A","B","B","C","C","D","E","F"] n = 2,A依然为最频繁任务，决定了关键点：
A _ _ A _ _ A --> A B C | A B C | A
加上一个|就很好理解了，竖线的前面都是可以插入单一任务的：
A B C D E F| A B C | A 或者 A B C D | A B C E F | A 又因为其他任务数量数肯定小于A的所以肯定可以处理完剩下的任务。
如果存在多个最频繁任务呢？["A","A","A","B","B","B","C"] n = 2,则可以理解为A B合并成了一个任务S
A B _ A B _ A B --> S _ S _ S 和上面的例子就是中间的_从2变成了1.
如果存在A B C D都出现3次，但是n=2
A B C D | A B C D | A B C D 已经是超出了n了所以其他任务在|前面插入即可。
func leastInterval(tasks []byte, n int) int {
count := [26]int{}
max, maxCount := 0, 0
for i := 0; i < len(tasks); i++ {
index := tasks[i] - 'A'
count[index] += 1
if max < count[index] {
max = count[index]
maxCount = 0
}
if max == count[index] {
maxCount++
}
}
slot := (max - 1) * (n - maxCount + 1)
todoTasks := len(tasks) - maxCount * max
emptySlot := Max(slot - todoTasks, 0)
return len(tasks) + emptySlot
}
func Max(a, b int) int {
if a > b {
return a
}
return b
}