LeetCode 621: Task Scheduler

Problem Description

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 3^rd interval, neither A nor B can be done, so you idle. By the 4^th 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 <= 10⁴
tasks[i] is an uppercase English letter.
0 <= n <= 100

Difficulty: Medium

Tags: array, hash table, greedy, sorting, heap (priority queue), counting

Rating: 83.62%

Solution Approach

The key insight comes from understanding what determines the minimum number of intervals needed:

The most frequent task(s) create a “skeleton” of the schedule
Other tasks can be inserted into the gaps between repetitions of the most frequent task
The minimum intervals needed is determined by either:
- The spacing required by the most frequent task
- The total number of tasks (if we have enough different tasks to fill the gaps)

Solution Explanation

Let’s examine the solution step by step:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Count the frequency of each task
        task_counts = Counter(tasks)

        # Find the maximum frequency
        max_freq = max(task_counts.values())
        
        # Count how many tasks have the maximum frequency
        max_count = sum(1 for task, count in task_counts.items() 
                       if count == max_freq)
        
        # Calculate minimum intervals needed
        min_intervals = max((max_freq - 1) * (n + 1) + max_count, len(tasks))
        
        return min_intervals

Breaking Down the Formula

The formula (max_freq - 1) * (n + 1) + max_count can be understood as follows:

max_freq - 1: Represents the number of gaps we need between the most frequent task
n + 1: Each gap must be at least n intervals, and we add 1 to include the task itself
max_count: Accounts for tasks that have the same maximum frequency

For example, with tasks = [“A”,“A”,“A”,“B”,“B”,“B”] and n = 2:

max_freq = 3 (both A and B appear 3 times)
max_count = 2 (two tasks, A and B, have frequency 3)
Formula: (3-1) * (2+1) + 2 = 2 * 3 + 2 = 8

We take the maximum of this value and len(tasks) because in cases with many different tasks, we might not need any idle intervals at all.

Complexity Analysis

The solution has the following complexity characteristics:

Time Complexity: $O(N)$ , where N is the length of the tasks array
- Counter() takes $O(N)$ to count all tasks
- Finding max frequency and count of max frequency tasks takes $O(26)$ = $O(1)$
Space Complexity: $O(1)$
- Counter stores at most 26 entries (one for each uppercase letter)
- All other variables use constant space