621.Task Scheduler

Solution 1: O(n)

class Solution {
    //O(n)
    //https://leetcode.com/problems/task-scheduler/discuss/104496/
    public int leastInterval(char[] tasks, int n) {
        if(n == 0){
            return tasks.length;
        }
        int[] count = new int[26]; 
        for(char t : tasks){
            count[t - 'A']++;
        }
        Arrays.sort(count);
        int i = 25;
        while(i >= 0 && count[i]==count[25]){
            i--;
        }
        return Math.max(tasks.length, (n + 1) * (count[25] - 1) + (25 - i));
    }
}

Solution 2: Priority Queue

The best time for construct a heap is O(n)

The usual time for construct a heap is O(nlogn)

The insert and remove cost is O(logn)

class Solution {
    public int leastInterval(char[] tasks, int n) {
        if(n == 0){
            return tasks.length;
        }

        int[] count = new int[26];
        for(char t :  tasks){
            count[t - 'A']++;
        }

        PriorityQueue<Integer> pQueue = new PriorityQueue<>(26, Collections.reverseOrder());
        for(int c : count){
            if(c > 0){
                pQueue.add(c);
            }
        }
        int timeCnt = 0;
        while(!pQueue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int tmpCnt = 0;
            for(int i = 0; i <= n; i++){
                if(!pQueue.isEmpty()){
                    int peekVal = pQueue.poll();
                    if(peekVal > 1){
                        tmp.add(peekVal - 1);
                    }
                }
                timeCnt++;
                if(pQueue.isEmpty() && (tmp.size() == 0)){
                    break;
                }
            }
            for(Integer i : tmp){
                pQueue.add(i--);
            }
        }
        return timeCnt;
    }
}