力扣 621 任务调度器

题意：给定一个任务列表和相同任务执行的冷冻间隔n，求执行完所有任务的最小的时间

思路：隔板法，把出现次数最多的一个task当作隔板

1. 找出最多task的个数max和出现次数为max的task的个数cnt，
2. 那么可能的interval即为，(max-1)*n （得到中间间隔的task总数＋max（隔开间隔的task数）＋cnt - 1（末尾出现次数为max的其他task的个数）
3. 返回可能的interval和总task的较大值

思想：数学方法

复杂度：时间O（n)，空间O(n)

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int len = tasks.length;
        if(len == 0)
            return 0;
        int max = 0;
        int sum = 0;
        HashMap<Character, Integer> map = new HashMap();// 可以用一个char array替代hashmap
        // 统计同一个task出现的个数，并找出出现最多的task
        for(int i=0;i<len;i++) {
            char cur = tasks[i];
            map.put(cur, map.getOrDefault(cur, 0) + 1);
            max = Math.max(map.get(cur), max);
        }
        int cnt = 0;
        // 找出出现最多的task的个数，并统计task总共的个数
        for(int value: map.values()) {
            if(value == max)
                cnt++;
            sum += value;
        }
        // 返回可能的interval和总共task的较大值
        return Math.max((max - 1) * n + max + cnt - 1, sum);
    }
}