Java Solution #PriorityQueue #CoolDownTable


  • 2

    A brief summary:

    • A valid task should be either in the waitingQueue or on the tasksTable
    • At the moment time, tasksTable removes the frozen task at time-1-n, and puts it back to the waitingQueue
    • At the end of each cycle, if a task is still valid, put it in the tasksTable

    When we say a task a valid, we mean there are remaining tasks of the same type waiting to be fulfilled. For example, task A is valid if there are 2 more task A waiting to be fulfilled.

    public class Solution {
        public int leastInterval(char[] tasks, int n) {
     
            Map<Character, Integer> tasksTable = new HashMap<>();
            for (char c : tasks) tasksTable.put(c, tasksTable.getOrDefault(c, 0)+1);
    
            // A task should be either in a waiting queue or on the cooldown table
            PriorityQueue<Character> waitingQueue = 
                    new PriorityQueue<>((c1, c2)->tasksTable.get(c2)-tasksTable.get(c1));
            for (Character c : tasksTable.keySet()) waitingQueue.add(c);
    
            // A task should be either in a waiting queue or on the cooldown table
            Map<Integer, Character> coolDownTable = new HashMap<>();
    
            int time = 0;
            while(!waitingQueue.isEmpty() || !coolDownTable.isEmpty()) {
                // Cool down and release the defrost task if any
                int releaseTime = time - n - 1;
                if (coolDownTable.containsKey(releaseTime)) {
                    waitingQueue.add(coolDownTable.remove(releaseTime));
                }
    
                if (!waitingQueue.isEmpty()) {
                    char task = waitingQueue.poll();
    
                    int remaining = tasksTable.get(task) - 1;
                    tasksTable.put(task, remaining);
    
                    if (remaining != 0) {
                        coolDownTable.put(time, task);
                    }
                }
    
                ++time;
            }
    
            return time;
        }
    }
    

  • 0
    H

    Nice solution. Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.