Java Solution, PriorityQueue and HashMap


  • 11
    1. Greedy - It's obvious that we should always process the task which has largest amount left.
    2. Put tasks (only their counts are enough, we don't care they are 'A' or 'B') in a PriorityQueue in descending order.
    3. Start to process tasks from front of the queue. If amount left > 0, put it into a coolDown HashMap
    4. If there's task which cool-down expired, put it into the queue and wait to be processed.
    5. Repeat step 3, 4 till there is no task left.
    public class Solution {
        public int leastInterval(char[] tasks, int n) {
            if (n == 0) return tasks.length;
            
            Map<Character, Integer> taskToCount = new HashMap<>();
            for (char c : tasks) {
                taskToCount.put(c, taskToCount.getOrDefault(c, 0) + 1);
            }
            
            Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);
            for (char c : taskToCount.keySet()) queue.offer(taskToCount.get(c));
            
            Map<Integer, Integer> coolDown = new HashMap<>();
            int currTime = 0;
            while (!queue.isEmpty() || !coolDown.isEmpty()) {
                if (coolDown.containsKey(currTime - n - 1)) {
                    queue.offer(coolDown.remove(currTime - n - 1));
                }
                if (!queue.isEmpty()) {
                    int left = queue.poll() - 1;
            	if (left != 0) coolDown.put(currTime, left);
                }
                currTime++;
            }
            
            return currTime;
        }
    }
    

  • 1

    @shawngao said in Java Solution, PriorityQueue and HashMap:

    Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);

    Get a little bit confused with the Integer queue. How do we identify the task with an Integer? Shouldn't we declare a Character queue instead?

    I have a solution following the similar idea but with a Character queue.
    https://discuss.leetcode.com/topic/93019/java-solution-priorityqueue-cooldowntable


  • 0

    Nice solution, one simple suggestion is to use
    Comparator.reverseOrder() instead of (i1,i2) -> i2-i1


  • 0

    @RunRunCode Not needed, since we care only about the frequency and the character is not used.
    We're just reducing the frequency in each iteration.


  • 0
    Y

    Awesome!

    Very concise and clear!


  • 0
    W

    What if we're asked to print out all possible schedule of the tasks? Anyone has some ideas?


Log in to reply
 

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