Solution: Task Scheduler

Statement

Given a character array tasks, where each character represents a unique task, and a positive integer n that represents the cooling period between any two identical tasks, find the minimum number of time units the CPU will need to complete all the given tasks. Each task requires one unit to perform, and the CPU must wait for at least n units of time before it can repeat the same task. During the cooling period, the CPU may perform other tasks or remain idle.

Constraints:

• $1 \leq$ tasks.length $\leq 1000$

• $0 \le$ n $\leq 100$

• tasks consists of uppercase English letters

Solution

The optimal strategy is to schedule the most frequent task first, then the second most frequent task, and so on. This is because we can estimate the maximum idle time once we’ve scheduled the most frequent task. In this solution, we calculate the minimum time required for a CPU to execute a sequence of tasks, with a cooling period between identical tasks. To calculate the total time the CPU will take to perform the given tasks, we will follow these steps:

• Store the frequency of each task and then sort them based on these frequencies. Begin by calculating the maximum possible idle time given by: $(\text{max frequency} - 1) \times \text{cooling period}$.
  Here, $\text{max frequency}$ refers to the highest frequency of any task in the sequence, and the $\text{cooling period}$ is the specified interval between identical tasks. This formula represents the maximum time the CPU could potentially remain idle between executions of tasks of the same type.

• Next, iterate over the sorted task frequencies and update the idle time accordingly by subtracting the idle time from the frequency of each task until the idle time becomes negative or all tasks have been processed. The adjustment to the idle time during each iteration is calculated as: $\text{idle time} = \text{idle time} - \min(\text{max frequency} - 1, \text{current frequency})$, where $\text{current frequency}$ represents the frequency of the task currently being processed.

• Finally, return the total time required, which is the sum of the length of the task sequence and the computed idle time, expressed as $\text{length of tasks} + \text{idle time}$.

Let’s look at the following slides to get a better understanding of the solution: