1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] taskCount = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            taskCount[tasks[i] - 'A'] += 1;
        }
        Arrays.sort(taskCount);
        int gaps = (taskCount[taskCount.length - 1] - 1) * n;
        for (int i = taskCount.length - 2; i >= 0 && gaps > 0; i--) {
            gaps -= Math.min(taskCount[taskCount.length - 1] - 1, taskCount[i]);
        }
        return gaps <= 0 ? tasks.length : gaps + tasks.length;
    }
}

这道题的思路是这样的. 我们先找到出现频率最高的jobs, 频率为fmax. 那么这些jobs之间肯定有fmax - 1个间隔. 这些间隔里面可以填充idle unit, 也可以填充其他job, 但是一定会有这么多间隔. 那么如果能够让其他的job把这些slots填满最好. 由于间隔时长是n, 那么一共有n * (fmax - 1)个slots等待被填充. 假设第一个间隔我们称为g1, 第二个间隔为g2…最后一个间隔为gn. 然后我们开始遍历每一种jobs, 看能不能把它们安排进这些slots中. 我们的原则是每种job, 它们是挨个填充每一个间隔. 比如来个job x, 出现m次. 那么第一个x在第一个间隔, 第二个x在第二个… 这就会有两种情况, 如果x的数量能把每一个间隔都放一个, 那么此时可能会剩下一个x或不剩下(因为x出现的频率可能和出现频率最高的那个job一样或者比它小), 这个剩下的先保留. 如果没填满, 那么下一种job接着往后填, 也就是不要直接再从第一个间隔开始. 比如上一种填到了第5个间隔, 那么就接着填第6个, 如果上一种填到了最后一个间隔, 那就从头开始填. 那这个第二种job有没有可能又来一遍每个间隔都有的情况呢? 有可能, 还是一样, 会剩下一个或者没有剩下, 剩下的就先保留. 按照这个思路填. 填到最后会有两种情况. 间隔全部都填满了, 此时每个间隔中没有相同类型的job. 现在剩下的jobs会有这两种情况. 一个是有些jobs压根还没安排, 还有就是之前有的jobs频率高, 会剩下一个. 没有安排上的jobs依旧按照上面说的规则去挨个插入每个间隔, 每个间隔都插入一种, 保证自己在每一个间隔都不会有重复. 剩余的那些因为频率高剩一个的, 统一放到最后去运行, 因为这些频率高的jobs都是不同的, 那么放在一起运行是没问题的.

我们来看一个例子.
比如[A A A A A B B B B B C C C D D D F E] n = 2
开始就是先这样排(_表示待被填的slot):
A _ _ A _ _ A _ _ A _ _ A
然后开始插入B(每个间隔插一个):
A B _ A B _ A B _ A B _ A
此时剩下一个B放到最后:
A B _ A B _ A B _ A B _ A B
然后插入C:
A B C A B C A B C A B _ A B
然后插入D(不从头开始, 接着后面的间隔插入):
A B C | A B C | A B C | A B D | A B
此时空填完了, 但是还有jobs没有填完, 于是继续:
A B C D | A B C D | A B C F | A B D E | A B
也就是还是按照一个间隔插一个之后换下一个间隔插的原则. 这样永远不会出现一个间隔出现多个某一种job类型的情况. 那些高频率多出来的jobs统一放到最后运行. 频率再高也不会多出两个及以上, 它们顶多频率和A的一样, 要不然它们就会被选为最高频率的job了. 如果和A的频率一样高, 那么一个间隔填一个只会剩下一个.

综上, 我们首先算出至少有的间隔, 然后看能不能把间隔填满, 如果可以, 那么剩下的jobs按照我们之前提到的方法继续安排上(未安排的还是插空, 之前多出来的统一安排到最后运行), 这样我们就能保证最小. 如果间隔填不满, 那么只能是加上idle time. 这些最高频率jobs之间的间隔是一定有的, 间隔的数量是固定的, 但是长度最短就是n, 最大不限, 否则就违背题意.

时间复杂度: O(n)
空间复杂度: O(1) 因为我们就使用了一个固定长度为26的数组.