Coding Interview PatternsTask Scheduler
MediumIntervals

Task Scheduler

Explanation & Solution

Practice Problem

Description

You are given an array of CPU tasks, each represented by a single uppercase letter, and a cooling interval n. Each CPU interval allows the CPU to either complete a task or remain idle. The same task cannot be executed again until at least n intervals have passed since its last execution.

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

Input:tasks = ["A","A","A","B","B","B"], n = 2
0
A
1
A
2
A
3
B
4
B
5
B

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. After completing task A, you must wait 2 intervals before executing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so the CPU idles. By the 4th interval, A can be executed again.

Constraints

  • 1 <= tasks.length <= 10^4
  • tasks[i] is an uppercase English letter
  • 0 <= n <= 100

Approach

Intervals pattern

1. Count Task Frequencies

  • Create a frequency array of size 26 (one slot per uppercase letter)
  • Iterate through the tasks array and count how many times each task appears

2. Find the Maximum Frequency

  • Determine maxFreq — the highest count among all tasks
  • This is the task that appears the most and creates the bottleneck for scheduling

3. Count Tasks with Maximum Frequency

  • Count maxCount — how many distinct tasks share the maximum frequency
  • For example, if both A and B each appear 3 times and that is the max, then maxCount = 2

4. Apply the Formula

  • The key formula is: (maxFreq - 1) * (n + 1) + maxCount
  • Why it works: Think of the schedule as a grid of frames
  • There are maxFreq - 1 full frames, each of width n + 1 (one slot for the task + n cooldown slots)
  • After the last frame, we only need to place the maxCount tasks that have the maximum frequency (no cooldown needed after the final occurrence)
  • Example with tasks = [A,A,A,B,B,B], n = 2:
  • maxFreq = 3, maxCount = 2
  • Frame layout: [A B _] [A B _] [A B]
  • Result: (3-1) * (2+1) + 2 = 2 * 3 + 2 = 8

5. Take the Maximum with tasks.length

  • The formula can undercount when there are many distinct tasks that fill all idle slots and overflow
  • In that case, no idle time is needed, and the answer is simply tasks.length
  • So the final answer is: Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount)

Complexity

  • Time: O(n) — one pass to count frequencies, constant work for 26 letters
  • Space: O(1) — the frequency array is always size 26 regardless of input size

Solution Code

Previous
Meeting Rooms II
Next
Minimum Number of Arrows to Burst Balloons