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:
tasks.length
n
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
. Here, refers to the highest frequency of any task in the sequence, and 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
, where 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
.
Let’s look at the following slides to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.