621. Task Scheduler

Link

Solution

1. Realize the answer would be the ( idel interval + taskCount)

2. Calculate the idel interval , we need to know how many space we can offer ex: 3 A 2 B 1C, n = 2 A _ _ A _ _ A

   empty space = n * (mostFrequency-1)

3. For including Specail case: Assume another B's frequency is also same as mostFrequency; ex: 3 A 3 B 2C n = 2 AB_ AB_AB X_X_X empty slot = (n - (mostFrequncyCount -1)) * (mostFrequcy-1)

 public int leastInterval(char[] tasks, int n) {
        int[] taskNums = new int[26];
        int taskCount = tasks.length;
        int mostFrequency = 0;
        int mostFrequencyCount = 0;
        for(char c : tasks){
            taskNums[c-'A']++;
            mostFrequency = Math.max(mostFrequency, taskNums[c-'A']);
        }
        for(int i =0; i<26; i++){
            if(taskNums[i] == mostFrequency) mostFrequencyCount++;
        }
        
        
        int slotCount = mostFrequency - 1;
        int slotSpace = n - (mostFrequencyCount-1);
        int totalSpace = slotCount * slotSpace;
        int idle = Math.max(0, totalSpace - (taskCount - mostFrequency * mostFrequencyCount));
        
        return idle + taskCount;
    }