Solution: Task Scheduler

Let's solve the Task Scheduler problem using the Merge Intervals pattern.

We'll cover the following

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≤ 1 \leq  tasks.length ≤1000 \leq 1000

  • 0≤0 \le n ≤100 \leq 100

  • tasks consists of uppercase English letters

Solution

The algorithm’s essence lies in minimizing idle time by strategically scheduling tasks based on their frequency. Starting with the most frequent tasks, we create a structure that potentially maximizes idle time, then reduce this idle time by incorporating less frequent tasks within the cooling periods.

To calculate the minimum 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, which is given by (Max frequency−1)×cooling period(\text{Max frequency} - 1) \times \text{cooling period}. Here, Max frequency\text{Max frequency} refers to the highest frequency of any task in the sequence, and cooling period\text{cooling period} is the specified interval between identical tasks. This formula represents the maximum time the CPU could 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 Idle Time−=min⁡(Max Frequency−1, Current Task Frequency)\text{Idle Time} -= \min(\text{Max Frequency} - 1, \text{ Current Task Frequency}), where Current Task Frequency\text{Current Task 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 length of tasks+Idle Time\text{length of tasks} + \text{Idle Time}.

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.