Task Scheduler medium

Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, and an integer n, representing the cooldown period between two same tasks (i.e., a task cannot be scheduled if the same task was scheduled less than n time units ago). Return the minimum number of units of times that the CPU will take to finish all the tasks.

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A -> B -> A -> B -> A -> B -> idle -> A Here's how the tasks are scheduled: [A, B, A, B, A, B, , A]

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 Explanation: No cooldown period, tasks can be executed consecutively.

Steps

1. Task Frequency: Count the frequency of each task using a map.
2. Max Frequency: Find the task with the maximum frequency (maxFreq). Count the number of tasks with this maximum frequency (maxFreqCount).
3. Idle Slots: Calculate the number of idle slots needed to accommodate the tasks with maximum frequency. This is given by (maxFreq - 1) * (n + 1). This formula represents the gaps needed between the maximum frequency tasks.
4. Remaining Tasks: Calculate the number of remaining tasks after placing the most frequent tasks.
5. Total Time: The total time is the maximum of the idle slots plus the number of tasks and the total number of tasks.

Explanation

The key to solving this problem is understanding how to optimally schedule the most frequent tasks to minimize idle time. By placing the most frequent tasks as far apart as possible (with the cooldown period), we ensure we're using the idle time efficiently. The formula (maxFreq - 1) * (n + 1) calculates the number of idle slots needed between the tasks with maximum frequency. We add maxFreqCount -1 because we need to separate maxFreqCount tasks. Each separation takes n+1 time slots (n for cooldown + 1 for the next task).

Code

function leastInterval(tasks: string[], n: number): number {
    const freqMap = new Map<string, number>();
    for (const task of tasks) {
        freqMap.set(task, (freqMap.get(task) || 0) + 1);
    }

    let maxFreq = 0;
    let maxFreqCount = 0;
    for (const freq of freqMap.values()) {
        if (freq > maxFreq) {
            maxFreq = freq;
            maxFreqCount = 1;
        } else if (freq === maxFreq) {
            maxFreqCount++;
        }
    }

    const idleSlots = (maxFreq - 1) * (n + 1);
    const remainingTasks = tasks.length - maxFreq * maxFreqCount;
    const totalTime = Math.max(idleSlots + maxFreqCount, tasks.length);

    return totalTime;
};

Complexity

• Time Complexity: O(N), where N is the number of tasks. This is because we iterate through the tasks once to count frequencies and then iterate through the frequencies.
• Space Complexity: O(1). The space used by the frequency map is constant as the number of unique tasks is limited by the alphabet size (26 in this case, assuming only uppercase letters). This means that space complexity is independent of the input size.