621. 任务调度器 (opens new window)

1.优先级队列

分析：创建一个二维数组保存每一个字母的任务次数、冷却时间。

同一种类型的任务在冷却时间内不能执行多次，因此调度策略如下，每次优先调度剩余任务次数最大的，且冷却时间为0的任务类型。也就说是优先考虑同一类型任务次数较多的任务，从而保证待命的时间最小。

class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<tasks.length;i++){
            char c=tasks[i];
            map.put(c,map.getOrDefault(c,0)+1);
        }
        int[][] nums=new int[map.size()][2];
        int index=0,res=0;
        for(Map.Entry<Character,Integer> entry: map.entrySet()){
            nums[index++][0]=entry.getValue();
        }
        while(true){
            //每轮排序，找出最大的未调度的程序
            Arrays.sort(nums,new Comparator<int[]>(){
                public int compare(int[] o1,int[] o2){
                    return o2[0]-o1[0];
                }
            });
            boolean finded=false;
            for(int i=0;i<nums.length;i++){
                if(nums[i][0]>0&&nums[i][1]==0){
                    nums[i][1]=n+1;
                    nums[i][0]--;
                    finded=true;
                    res++;
                    break;
                }
            }
            if(!finded) res++;
            boolean check=false;
            //冷却时间减一
            for(int i=0;i<nums.length;i++){
                if(nums[i][1]>0){
                    nums[i][1]--;
                }
                if(nums[i][0]>0) check=true;
            }
            //判断完成所有任务
            if(!check) break;
        }
        return res;
    }
}