JavaScript solution using priority queue


  • 0
    D
    /**
     * @param {character[]} tasks
     * @param {number} n
     * @return {number}
     */
    var leastInterval = function(tasks, n) {
        
        let arr = [];
        let map = {};
        
        for(let i = 0; i < tasks.length; i++){
            map[tasks[i]] = map[tasks[i]] ? map[tasks[i]] + 1 : 1;
        }
        
        for(let key in map){
            var item = { value: key, count: map[key] };
            arr.push(item);
        }
        
        let queue = new TinyQueue(arr, count_comparator);
        let cycles = 0;
        let top = null;
        
        while(queue.length){
            let k = n+1;
            let temparr = [];
            
            while(k>0 && queue.length){
                top = queue.pop();
                top.count = top.count - 1;
    
                if(top.count > 0){
                   temparr.push(top);
                }
                
                cycles++;
                k--;
            }
            
            for(let item of temparr){
                queue.push(item);
            }
            
            if(!queue.length){
               break;
            }
            
            cycles += k;
        }
        
        return cycles;
       
        function count_comparator(a, b){
            return b.count - a.count;
        }
        
    };
    
    
    
    
    
    
    
    
    // Priority Queue
    // https://github.com/mourner/tinyqueue
    
    function TinyQueue(data, compare) {
        if (!(this instanceof TinyQueue)) return new TinyQueue(data, compare);
    
        this.data = data || [];
        this.length = this.data.length;
        this.compare = compare || defaultCompare;
    
        if (this.length > 0) {
            for (var i = (this.length >> 1); i >= 0; i--) this._down(i);
        }
    }
    
    function defaultCompare(a, b) {
        return a < b ? -1 : a > b ? 1 : 0;
    }
    
    TinyQueue.prototype = {
    
        push: function (item) {
            this.data.push(item);
            this.length++;
            this._up(this.length - 1);
        },
    
        pop: function () {
            if (this.length === 0) return undefined;
    
            var top = this.data[0];
            this.length--;
    
            if (this.length > 0) {
                this.data[0] = this.data[this.length];
                this._down(0);
            }
            this.data.pop();
    
            return top;
        },
    
        peek: function () {
            return this.data[0];
        },
    
        _up: function (pos) {
            var data = this.data;
            var compare = this.compare;
            var item = data[pos];
            //var tempN = N;
            
            while (pos > 0) {
                //tempN--;
                var parent = (pos - 1) >> 1;
                var current = data[parent];
                if (compare(item, current) >= 0) break;
                data[pos] = current;
                pos = parent;
                
            }
    
            data[pos] = item;
        },
    
        _down: function (pos) {
            var data = this.data;
            var compare = this.compare;
            var halfLength = this.length >> 1;
            var item = data[pos];
    
            while (pos < halfLength) {
                var left = (pos << 1) + 1;
                var right = left + 1;
                var best = data[left];
    
                if (right < this.length && compare(data[right], best) < 0) {
                    left = right;
                    best = data[right];
                }
                if (compare(best, item) >= 0) break;
    
                data[pos] = best;
                pos = left;
            }
    
            data[pos] = item;
        }
    };
    
    

Log in to reply
 

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