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 units time ago). Return the least 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

[A][B][A][B][A][B][][A]

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 Explanation: No cooldown is needed, so you can schedule them as:

[A][A][A][B][B][B]

Steps to Solve

1. Frequency Count: Count the frequency of each task. This helps determine which tasks are the bottlenecks.
2. Max Frequency: Find the task with the maximum frequency (maxFreq).
3. Max Frequency Count: Count how many tasks have the maximum frequency (maxFreqCount).
4. Idle Slots: Calculate the number of idle slots needed to satisfy the cooldown requirement for the most frequent task. This is based on the maxFreq and n.
5. Total Time: Calculate the total time needed. This is the sum of the time taken by the most frequent tasks, the idle slots, and the time for the remaining tasks.

Explanation

The key to solving this problem is understanding that the most frequent task dictates the overall schedule. We need to strategically place idle slots to satisfy the cooldown constraint for this most frequent task. The rest of the tasks can then be filled in efficiently.

The formula for idle slots is derived as follows: Consider a task with maxFreq occurrences. To place them with a cooldown of n, we need (maxFreq - 1) * (n + 1) idle slots. We subtract 1 from maxFreq because the last occurrence of the task doesn't require an idle slot after it. We add 1 to n because it represents the gap between tasks (n slots plus the task itself). However, this can be an overestimate if there are not enough other tasks to fill these slots. The Math.max(0, ...) ensures we don't get a negative number of idle slots.

Code (Java)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char task : tasks) {
            freqMap.put(task, freqMap.getOrDefault(task, 0) + 1);
        }

        int maxFreq = 0;
        for (int freq : freqMap.values()) {
            maxFreq = Math.max(maxFreq, freq);
        }

        int maxFreqCount = 0;
        for (int freq : freqMap.values()) {
            if (freq == maxFreq) {
                maxFreqCount++;
            }
        }

        int idleSlots = Math.max(0, (maxFreq - 1) * (n + 1) - (maxFreqCount-1)); //Correct formula for Idle slots
        int totalTime = (maxFreq - 1) * (n + 1) + maxFreqCount;


        return Math.max(totalTime, tasks.length); //Handle cases with enough other tasks to fill idle slots
    }
}

Complexity

• Time Complexity: O(N), where N is the number of tasks. This is dominated by the frequency counting step.
• Space Complexity: O(1), as the HashMap size is limited by the number of unique tasks (at most 26 in this case, assuming only uppercase English letters). The space used is constant regardless of the input size.