Java PriorityQueue Approach with detailed comments


  • 0
    J

    Divide the timeline into cycles by n. Use priorityqueue to figure out which task get executed first in each cycle.

    class Execution implements Comparable<Execution> {
        int times; // times remained to execute
        int lastExe; // the last execution time (to determine if in cool down)
        public Execution(int times, int lastExe) {
            this.times = times;
            this.lastExe = lastExe;
        }
        @Override
        public int compareTo(Execution that) {
            if (that.times != this.times) {
                // the task with more remaining times should have higher priority
                return that.times - this.times;
            } else {
                // if of same priority, we should keep the previous execution order 
                // (consider ['A','B','C','A','B','C] with n = 2)
                return this.lastExe - that.lastExe;
            }
        }
    }
    
    public class Solution {
        public int leastInterval(char[] tasks, int n) {
            n++;
            char[] counts = new char[26];
            for (char task : tasks) {
                counts[task - 'A']++;
            }
            // the priority queue to determine which get executed first
            PriorityQueue<Execution> q = new PriorityQueue<>();
            // a buffer for storing tasks being executed in each cycle.
            // It's impossible to execute the same task twice in one cycle.
            Queue<Execution> q2 = new LinkedList<>(); 
            for (char task = 'A'; task <= 'Z'; task++) {
                int count = counts[task - 'A'];
                if (count > 0) {
                    q.offer(new Execution(count, -n));
                }
            }
            int time = 0;
            while (!q.isEmpty() || !q2.isEmpty()) {
                Execution next = q.poll();
                if (next == null) {
                    // idle 
                    time++;
                } else if (time - next.lastExe < n) {
                    // next task is still in cool down
                    q2.offer(next);
                } else {
                    // execute next task
                    if (next.times > 1) {
                        // only task with remaining times would be buffered to q2
                        next.times--;
                        next.lastExe = time;
                        q2.offer(next);
                    }
                    time++;
                }
                if (time % n == 0) {
                    // The beginning of next cycle: 
                    // Clear out q2 and offer the task back to the priority queue
                    while (!q2.isEmpty()) {
                        q.offer(q2.poll());
                    }
                }
            }
            return time;
        }
    }
    

Log in to reply
 

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