You are given:

An array of CPU tasks, each represented by an uppercase letter
A non-negative cooling interval n

The CPU can execute one task per unit time, but the same task must have at least n units of cooling time before it can run again.

Your goal:
Return the minimum number of time intervals needed to execute all tasks.

---

Understanding the Problem

Example:

tasks = [A, A, A, B, B, B], n = 2
Output = 8

Valid schedule:
A B idle A B idle A B
Total intervals = 8

Why idle?
Because between any two A’s, the CPU needs at least 2 cooldown slots.

---

Approach (Explained in Simple Language)

The key observation:

The task that appears most frequently determines the minimum schedule length.

Let:

maxFreq = frequency of the most frequent task
maxCount = how many tasks share that frequency

Example:

A: 3
B: 3
C: 1

maxFreq = 3
maxCount = 2 (A and B)

Now understand the pattern:

For the most frequent task(s), we create blocks:

Each block (except last) must contain:
One task instance
Then n cooldown slots

Number of blocks = maxFreq − 1

Structure:

[Task] [ _ _ ]
[Task] [ _ _ ]
[Task]

Total slots created = (maxFreq – 1) * (n + 1)

Finally, in the last block, we place maxCount tasks.

Final formula:

minimum time =
max( total tasks , (maxFreq – 1) * (n + 1) + maxCount )

Why take max?
Because if there are many different tasks, they may fill idle slots so that the raw number of tasks is the larger value.

---

Java Code

import java.util.*;

public class TaskScheduler {

    public int leastInterval(char[] tasks, int n) {

        int[] freq = new int[26];

        for (char t : tasks) {
            freq[t - 'A']++;
        }

        Arrays.sort(freq);

        int maxFreq = freq[25];

        int maxCount = 0;
        for (int f : freq) {
            if (f == maxFreq) {
                maxCount++;
            }
        }

        int intervals = (maxFreq - 1) * (n + 1) + maxCount;

        return Math.max(intervals, tasks.length);
    }

    public static void main(String[] args) {
        TaskScheduler solution = new TaskScheduler();
        char[] tasks = {'A','A','A','B','B','B'};
        System.out.println(solution.leastInterval(tasks, 2));
    }
}

---

Dry Run

Input:

tasks = [A, A, A, B, B, B], n = 2

Count frequencies:

A = 3
B = 3
Others = 0

Sorted frequencies:
[0 … 0, 3, 3]

maxFreq = 3
maxCount = 2

---

Step 1: Apply the formula

intervals = (maxFreq – 1) * (n + 1) + maxCount
intervals = (3 – 1) * (2 + 1) + 2
intervals = 2 * 3 + 2
intervals = 8

Total tasks length = 6

Final answer = max(8, 6) = 8

---

Visualizing the block formation

There are 3 occurrences of the top tasks A and B.

Blocks:

[A, B] _ _
[A, B] _ _
[A, B]

Between each pair of A/B groups you need space for n = 2 cooldowns.

Fill tasks:

Row 1: A B idle idle
Row 2: A B idle idle
Row 3: A B

Total timeline length = 8

---

Why This Approach Works

The bottleneck is how fast we can schedule the most frequent tasks.
If one task occurs many times, those occurrences must be spaced at least n units apart.

This creates a structure of blocks:
(maxFreq – 1) blocks, each block of size (n + 1)

Then we place all equally frequent tasks in the last block.

If there are plenty of other tasks, they fill idle spaces, and the total time becomes total number of tasks.
So the maximum of both values determines the answer.

Time complexity: O(26 log 26) = O(1)
Space complexity: O(1)