Skip to content

621. Task Scheduler

Intuition

Notice that the needed CPU cycles is only dependent on the count of the most frequent character.

Approach

For example:

tasks = ["A","A","A","B"], n = 2

Schedule:

A -> B -> idle -> A -> idle -> idle -> A

Here we clearly see that the number of B does not affect the needed CPU cycles. It is solely controlled by the most dominant character(s) (‘A’).

Hence we can deduce that the needed CPU cycles is:

 (highestFrequency - 1) * (n + 1)

In which:
(n+1) is the idles needed between two same tasks
highestFrequency - 1 is the occurrences of the most frequent characters minus 1 (as the last task does not need idle time).

We have two more things to account for:

  1. More than one character can have the same frequency:
    We will plus one cycle for every character that have the same max frequency because of the trailing tasks at the end after we have distributed all the idle times.
  2. n maybe smaller than the number of available tasks: Then we will return the number of tasks because that is the least number of CPU cycles we need.

Code

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] fre = new int[26];
        int max = 0;
        for(char c : tasks) {
            fre[c - 'A']++;
        }
        for(int i : fre) {
            max = Math.max(max, i);
        }

        // free slots
        int emptySlots = (max - 1) * (n + 1);
        int sameFreq = 0;

        for(int i : fre) {
            if(i == max) {
                sameFreq++;
            }
        }

        emptySlots += sameFreq;

        return Math.max(emptySlots, tasks.length);
    }
}
Last update : February 17, 2024
Created : February 17, 2024

Comments