Task Scheduler

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there’s a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

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

Example 1:

Input: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = [“A”,“C”,“A”,“B”,“D”,“B”], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = [“A”,“A”,“A”, “B”,“B”,“B”], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

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

Approach: Greedy with Frequency Formula (Optimal Solution)

Algorithm

1. Count the frequency of each task
2. Find the maximum frequency maxFreq and how many tasks share that maximum (maxCount)
3. The minimum intervals can be computed with a formula: intervals = max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount)
4. Return the larger of the two values

Time & Space Complexity

• Time Complexity: O(n) - counting frequencies and scanning the frequency array
• Space Complexity: O(1) - fixed-size frequency array of 26 letters

Java Implementation

public class TaskScheduler {

    /**
     * Return the minimum number of CPU intervals to complete all tasks.
     * @param tasks Array of task labels
     * @param n Cooldown interval between same tasks
     * @return Minimum number of intervals
     */
    public static int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];

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

        int maxFreq = 0;
        int maxCount = 0;

        for (int f : freq) {
            if (f > maxFreq) {
                maxFreq = f;
                maxCount = 1;
            } else if (f == maxFreq) {
                maxCount++;
            }
        }

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

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

    // Test method
    public static void main(String[] args) {
        char[] tasks1 = {'A', 'A', 'A', 'B', 'B', 'B'};
        int n1 = 2;
        System.out.println("Input: tasks = [\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], n = 2");
        System.out.println("Output: " + leastInterval(tasks1, n1)); // Expected: 8

        char[] tasks2 = {'A', 'C', 'A', 'B', 'D', 'B'};
        int n2 = 1;
        System.out.println("Input: tasks = [\"A\",\"C\",\"A\",\"B\",\"D\",\"B\"], n = 1");
        System.out.println("Output: " + leastInterval(tasks2, n2)); // Expected: 6

        char[] tasks3 = {'A', 'A', 'A', 'B', 'B', 'B'};
        int n3 = 3;
        System.out.println("Input: tasks = [\"A\",\"A\",\"A\", \"B\",\"B\",\"B\"], n = 3");
        System.out.println("Output: " + leastInterval(tasks3, n3)); // Expected: 10
    }
}

Example Walkthrough

For tasks = ["A","A","A","B","B","B"], n = 2:

1. Frequencies: A=3, B=3
2. maxFreq = 3, maxCount = 2
3. intervals = (3 - 1) * (2 + 1) + 2 = 2 * 3 + 2 = 8
4. tasks.length = 6, so the answer is max(8, 6) = 8

Sequence: A -> B -> idle -> A -> B -> idle -> A -> B.

Key Points

1. Most Frequent Task Governs: The busiest task dictates the minimum scheduling slots
2. Formula: (maxFreq - 1) * (n + 1) + maxCount
3. No Idle Needed: If there are enough other tasks to fill the gaps, the answer is simply tasks.length
4. maxCount: Tasks sharing the maximum frequency fill the last row of the schedule
5. O(1) Space: The alphabet is fixed at 26 letters