Java PriorityQueue O(nlgn) solution


  • 0
    Z
        class P {
            int count, start;
            public P (int count) {
                this.count = count;
                this.start = 0;
            }
        }
        
        public int leastInterval(char[] tasks, int n) {
            int result = 0, size = tasks.length, i;
            PriorityQueue<P> pq = new PriorityQueue<P>(new Comparator<P>() {
               public int compare (P p1, P p2) {
                   if (p1.start != p2.start)
                     return p1.start - p2.start;
                   else
                    return p2.count - p1.count;
               } 
            });
            int[] count = new int[26];
            for (i=0;i<size;i++)
                count[tasks[i] - 'A']++;
            for (i=0;i<26;i++)
                if (count[i] > 0)
                    pq.add(new P(count[i]));
            P p;
            
            while (!pq.isEmpty()) {
                p = pq.poll();
                if (p.start >= result) {
                    result = p.start + 1;
                } else {
                    p.start = result;
                    pq.add(p);
                    continue;
                }
                
                p.count--;
                if (p.count > 0) {
                    p.start = result + n;
                    pq.add(p);
                }
            }
            return result;
        }
    }

Log in to reply
 

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