0621-task-scheduler.js

/**
 * https://leetcode.com/problems/task-scheduler/
 * Time O(N * log(N)) | Space O(N)
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function (tasks, n) {
    const frequencyMap = getFrequencyMap(tasks);
    const maxHeap = getMaxHeap(frequencyMap);

    return getMinimumCpuIntervals(maxHeap, n);
};

var getFrequencyMap = (tasks, frequencyMap = new Array(26).fill(0)) => {
    for (const task of tasks) {
        const index = task.charCodeAt(0) - 'A'.charCodeAt(0);

        frequencyMap[index]++;
    }

    return frequencyMap;
};

const getMaxHeap = (frequencyMap, maxHeap = new MaxPriorityQueue()) => {
    for (const frequency of frequencyMap) {
        const hasFrequency = 0 < frequency;
        if (hasFrequency) maxHeap.enqueue(frequency);
    }

    return maxHeap;
};

const getMinimumCpuIntervals = (maxHeap, n, cpuIntervals = [0]) => {
    while (!maxHeap.isEmpty()) {
        const { iterations, coolingPeriodQueue } = execute(
            n,
            maxHeap,
            cpuIntervals,
        );

        reQueueCoolingPeriod(coolingPeriodQueue, maxHeap);

        if (!maxHeap.isEmpty()) cpuIntervals[0] += iterations;
    }

    return cpuIntervals[0];
};

const execute = (
    n,
    maxHeap,
    cpuIntervals,
    iterations = n + 1,
    coolingPeriodQueue = new Queue(),
) => {
    while (0 < iterations && !maxHeap.isEmpty()) {
        const frequency = maxHeap.dequeue().element;

        const hasFrequency = 0 < frequency - 1;
        if (hasFrequency) coolingPeriodQueue.enqueue(frequency - 1);

        cpuIntervals[0]++;
        iterations--;
    }

    return { iterations, coolingPeriodQueue };
};

const reQueueCoolingPeriod = (coolingPeriodQueue, maxHeap) => {
    while (!coolingPeriodQueue.isEmpty()) {
        maxHeap.enqueue(coolingPeriodQueue.dequeue());
    }
};

/**
 * https://leetcode.com/problems/task-scheduler/
 * Time O(N) | Space O(1)
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function (tasks, n) {
    const frequencyMap = getFrequencyMap(tasks);
    const maxFrequency = getMaxFrequency(frequencyMap);
    const mostFrequentTask = getMostFrequentTask(frequencyMap, maxFrequency);
    const interval = (maxFrequency - 1) * (n + 1) + mostFrequentTask;

    return Math.max(tasks.length, interval);
};

var getFrequencyMap = (tasks, frequencyMap = new Array(26).fill(0)) => {
    for (const task of tasks) {
        const index = task.charCodeAt(0) - 'A'.charCodeAt(0);

        frequencyMap[index]++;
    }

    return frequencyMap;
};

const getMaxFrequency = (frequencyMap, maxFrequency = 0) => {
    for (const frequency of frequencyMap) {
        maxFrequency = Math.max(maxFrequency, frequency);
    }

    return maxFrequency;
};

const getMostFrequentTask = (
    frequencyMap,
    maxFrequency,
    mostFrequentTask = 0,
) => {
    for (const frequency of frequencyMap) {
        const isSame = frequency === maxFrequency;
        if (isSame) mostFrequentTask++;
    }

    return mostFrequentTask;
};