class Solution {
    // 贪心
    // 先执行次数最多的任务，可以充分利用任务之间的间隔。时间最短
    // 每次执行次数最多的任务，考虑优先队列，大根堆
    public int leastInterval(char[] tasks, int n) {
       PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);
       int[] count = new int[26];
       int res = 0;
       for (int i = 0; i < tasks.length; i++) { //对任务计数
            count[tasks[i] - 'A']++;
       }
       for (int tmp : count) { // 出现次数大于0的元素才意味着任务需要完成
        if (tmp > 0) {
             pq.offer(tmp);
        }
           
       }
       while (!pq.isEmpty()) {
          List<Integer> list = new ArrayList<>(); // list记录一个间隔内完成的任务
          for (int i = 0; i <= n; i++) {
            if (!pq.isEmpty()) {
                list.add(pq.poll());
            } 
         }
         for (int t : list) {
            if ( --t > 0) {
                pq.offer(t);
            }
         }
         res += pq.isEmpty() ? list.size() : n + 1;
       } 
       return res;
    }
    // public int leastInterval(char[] tasks, int n) {
    //     // 统计每种任务的出现次数
    //     int[] count = new int[26];
    //     for (char task : tasks) {
    //         count[task - 'A']++;
    //     }

    //     // 创建一个优先队列,存储每种任务的下一次执行时间
    //     PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    //     for (int c : count) {
    //         if (c > 0) {
    //             pq.offer(c);
    //         }
    //     }

    //     int time = 0;
    //     while (!pq.isEmpty()) {
    //         // 创建一个临时列表,存储当前时间可以执行的任务
    //         java.util.List<Integer> temp = new java.util.ArrayList<>();
    //         for (int i = 0; i <= n; i++) {
    //             if (!pq.isEmpty()) {
    //                 temp.add(pq.poll());
    //             }
    //         }

    //         // 将当前时间可以执行的任务加回优先队列,并更新它们的下一次执行时间
    //         for (int t : temp) {
    //             if (--t > 0) {
    //                 pq.offer(t);
    //             }
    //         }

    //         // 如果优先队列为空,说明所有任务已经完成,返回当前时间
    //         time += pq.isEmpty() ? temp.size() : n + 1;
    //     }

    //     return time;
    // }
}