leetcode 621. 任务调度器 中等 贪心

题目：

分析：相同种类的任务之间必须间隔n个单位的时间，根据这个题目条件，需要想到应优先执行个数最多的某个种类的任务，因为如果先执行个数少的任务，那么最终会剩下个数多的任务，间隔时间就会花费很多了。既然思路是按个数优先执行，那么就需要排序了，并且排序要动态变化，因为随着任务的执行，该种类任务会减少，想到优先队列，执行了某类任务，那么该类任务数在队列中要减1。
可以按轮来进行任务的安排，每轮最多可以取n+1个任务，因为如果任务种类大于n可以再安排一个任务并且下一轮第一个任务必定符合间隔n个单位的时间，如果任务种类不大于n，那么就相当于在冷却，不影响下一轮的进行和正确性。可以验证正确性，当前这轮第n个执行的任务，说明前n-1个任务的种类数量比此任务种类数多，所以一轮一轮的进行，同种类间必定有n个单位时间的冷却

代码：

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for(char c : tasks){
            counts[c - 'A'] ++;
        }
        //按降序排列
        Queue<Integer> queue = new PriorityQueue<>(26, Collections.reverseOrder());
        for(int count : counts){
            if(count > 0){
                queue.add(count);
            }
        }
        int time = 0;
        while(!queue.isEmpty()){
            int i = 0;
            List<Integer> list = new ArrayList<>();
            //最多可取n+1个任务
            while(i <= n){
                if(!queue.isEmpty()){
                    if(queue.peek() > 1){
                    	//如果该类任务数>1, 减1后最终放回队列中
                        list.add(queue.poll() - 1);
                    }else{
                        queue.poll();
                    }
                }
                time++;
                if(queue.isEmpty() && list.size() == 0){
                	//说明所有任务在本轮都剩1个，不需要再放回队列
                    break;
                }
                i++;
            }
            for(int temp : list){
                queue.add(temp);
            }
        }
        return time;
    }
}