【leetcode】任务调度器

题目：

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

提示：

任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。

思路：

(1）先找出现次数最多的字母，假设为A，出现m次，要求字母间隔大于n。那么先将A按照给定间隔排好后的长度为(m-1)(n+1) + 1,（m-1）是因为m个A之间有（m-1）块空格。（n+1）是因为每块空格长度为n，在加上字母A，一共n+1,最后一个+1是最后一个字母A。比如字母A出现3次，间隔为2，则A排好后为
A _ _ A _ _ A
（2）接下来排的时候只需要依次将频率小的字母插入这些空格中，注意插的时候要先插满第二位的空格，再插第三位的空格，以此类推，且频率高的字母先插。
（3）上面说的是大部分情况，但是还会出现两种特殊情况：
3.1.最大频率的字母不止一个，比如A，B都出现了3次，则此时A，B排好后为AB _ _ AB _ _ AB
会发现此时长度多了一个长度（最后一个B的长度），因此此时的总长度应该为(m-1)(n+1)+count ,count为最大频率的字母个数，在这里为2。上面的（1）可以认为是count=1的一个特例
3.2.当中间所有的空格都被填满了还没有插入所有元素，此时需要将剩余元素依次插入到每块的后面去（这样可以保证彼此间的间隔大于n，相当于是拓宽了部分块的间隔），比如AAABBCCD 先得到ABCABCA，此时还有一个D没有插入，则插到每个块后面去，得到ABCDABCA，此时会发现其实这个长度就是原数组的长度。

java代码：

class Solution {
    public int leastInterval(char[] tasks, int n) {
 
        Map<Character, Integer> map = new HashMap<>();
        int m = 0;
        for (char c : tasks) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
            m = Math.max(m, map.get(c));
        }
 
        int res = (m - 1) * (n + 1);  //第（1）种情况
 
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == m) { //第（3）-1的情况，第一种中的+1是在这里加的
                res++;
            }
        }
 
        return Math.max(res, tasks.length); //第（3）-2的情况
    }
}