Solution: Task Scheduler

Let's solve the Task Scheduler problem using the Knowing What to Track pattern.

We'll cover the following

Statement

You are given an array of CPU tasks represented by uppercase letters (A to Z) and an integer n, which denotes the cooling period required between any two identical tasks. Each task takes exactly one CPU interval to execute. Therefore, each CPU interval can either perform a task or remain idle. Tasks can be executed in any order, but the same task must be separated by at least n intervals.

Determine the minimum number of CPU intervals required to complete all tasks.

Constraints:

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

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

  • tasks consists of uppercase English letters

Solution

The core idea of this solution is to minimize the number of CPU intervals by strategically scheduling tasks based on their frequency. To optimize scheduling, we schedule the most frequent task first, ensuring that its occurrences are separated by n units of time. This guarantees maximum spacing, creating idle slots that can be filled with less frequent tasks. In the end, the total time required is determined by the sum of all tasks and any remaining idle slots, giving the minimum number of CPU intervals needed to complete all tasks.

Using the intuition above, we implement the algorithm as follows:

  1. Initialize an array, frequencies, of size 2626 to store the frequency of each task.

  2. Count the occurrences of each task in the tasks array and store them in frequencies.

  3. Sort frequencies in descending order.

  4. Compute the maximum number of gaps, maxGaps, by subtracting 1 from the frequency of the most frequent task. This represents the number of gaps between the tasks after scheduling the most frequent task.

  5. Compute idleSlots as maxGaps * n, representing the the maximum number of spare slots available after scheduling the most frequent task.

  6. Iterate over the remaining task frequencies (excluding the most frequent task) and reduce idleSlots by the minimum of maxGaps and the current frequency. We take the minimum because if multiple tasks share the same maximum frequency, an extra idle slot is subtracted, even though one instance of that task will not be scheduled in the idle gaps but rather after the already scheduled most frequent task.

  7. Ensure that idleSlots is not negative after the loop terminates, as it is being decremented within the loop.

  8. Return the sum of the length of the tasks array and idleSlots as the minimum number of CPU intervals required to complete all tasks.

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.