LeetCode 621 - Task Scheduler

The Task Scheduler problem asks us to determine the minimum number of CPU intervals required to complete a list of tasks with a cooling constraint. Each task is represented by an uppercase letter A-Z. The CPU can execute one task per interval or remain idle.

leetcodemediumarrayhash-tablegreedysortingheap-(priority-queue)counting

LeetCode Problem 621

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting

Solution

Problem Understanding

The Task Scheduler problem asks us to determine the minimum number of CPU intervals required to complete a list of tasks with a cooling constraint. Each task is represented by an uppercase letter A-Z. The CPU can execute one task per interval or remain idle. After executing a task, the CPU must wait at least n intervals before executing the same task again.

The input consists of an array of tasks and an integer n representing the cooling period. The output is a single integer representing the minimum number of intervals needed to complete all tasks while satisfying the cooling requirement.

Key constraints include: tasks can be repeated, tasks can be executed in any order, and the CPU can be idle. The number of tasks can be up to 10^4, and the cooling period n can be as high as 100. This means a naive simulation that attempts every possible task order is not feasible. Important edge cases include n = 0 (no cooling required) and arrays with many repetitions of a single task (which could require many idles).

Approaches

Brute Force

A brute-force approach would attempt to simulate every possible task execution order. At each interval, we would try to select a task that is not in the cooling period, and if no task is available, the CPU idles. We would continue until all tasks are completed. This approach guarantees correctness, but it has exponential time complexity because we must explore all permutations of task order while respecting the cooling constraints. It is clearly too slow for tasks.length = 10^4.

Optimal Approach

The key insight is that the minimum number of intervals is determined by the most frequent task. If a task appears f_max times, then there must be at least f_max - 1 full cycles of length n + 1 to separate occurrences of this task. Each cycle contains the task itself plus n idle slots or other tasks.

The formula for the minimum intervals is:

max(len(tasks), (f_max - 1) * (n + 1) + n_max)

Where n_max is the number of tasks that appear f_max times. This accounts for cases where multiple tasks share the maximum frequency, filling the last cycle without extra idles.

This approach uses a hash map to count frequencies and simple arithmetic to compute the minimum intervals, giving a linear-time solution with constant space relative to the alphabet size (26).

Approach Time Complexity Space Complexity Notes
Brute Force O(tasks!) O(tasks) Simulates every order; too slow
Optimal O(N) O(1) Counts frequencies and applies formula; efficient for large N

Algorithm Walkthrough

  1. Count the frequency of each task using a hash map. This allows us to determine which tasks are most frequent.
  2. Identify the maximum frequency f_max of any task.
  3. Count the number of tasks that have the maximum frequency (n_max). This helps determine how many tasks will occupy the last cycle.
  4. Calculate the minimum number of intervals using the formula (f_max - 1) * (n + 1) + n_max. This represents the cycles needed to space the most frequent tasks and fill them with other tasks or idle slots.
  5. Compare the calculated interval with the total number of tasks. The minimum intervals cannot be smaller than the total tasks because tasks executed without idles simply use one interval each. Return the maximum of the two.

Why it works: By focusing on the task(s) with the maximum frequency, we ensure all cooling constraints are respected. The formula arranges these tasks optimally, and any remaining tasks can fill idle slots or additional positions. This guarantees the computed interval is minimal.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0:
            return len(tasks)
        
        freq = Counter(tasks)
        f_max = max(freq.values())
        n_max = sum(1 for count in freq.values() if count == f_max)
        
        intervals = (f_max - 1) * (n + 1) + n_max
        return max(intervals, len(tasks))

The Python implementation first handles the edge case n = 0, which requires no idling. The Counter object computes task frequencies. We identify the maximum frequency and count tasks sharing this frequency. The formula calculates the minimum intervals, and the max function ensures we never return fewer intervals than tasks.

Go Solution

func leastInterval(tasks []byte, n int) int {
    if n == 0 {
        return len(tasks)
    }

    freq := make([]int, 26)
    for _, task := range tasks {
        freq[task-'A']++
    }

    f_max := 0
    for _, f := range freq {
        if f > f_max {
            f_max = f
        }
    }

    n_max := 0
    for _, f := range freq {
        if f == f_max {
            n_max++
        }
    }

    intervals := (f_max - 1) * (n + 1) + n_max
    if intervals < len(tasks) {
        return len(tasks)
    }
    return intervals
}

The Go solution mirrors Python. We use a fixed-size array of 26 for task frequencies and iterate to find f_max and n_max. The final formula computes the intervals, and the check against len(tasks) ensures correctness.

Worked Examples

Example 1: tasks = ["A","A","A","B","B","B"], n = 2

Task frequencies: A=3, B=3

f_max = 3, n_max = 2

Intervals = (3-1)_(2+1)+2 = 2_3+2 = 8

Maximum of intervals and len(tasks) = max(8,6) = 8

Example 2: tasks = ["A","C","A","B","D","B"], n = 1

Task frequencies: A=2, B=2, C=1, D=1

f_max = 2, n_max = 2

Intervals = (2-1)_(1+1)+2 = 1_2+2 = 4

Maximum of intervals and len(tasks) = max(4,6) = 6

Example 3: tasks = ["A","A","A","B","B","B"], n = 3

Task frequencies: A=3, B=3

f_max = 3, n_max = 2

Intervals = (3-1)_(3+1)+2 = 2_4+2 = 10

Maximum of intervals and len(tasks) = max(10,6) = 10

Complexity Analysis

Measure Complexity Explanation
Time O(N) Counting frequencies takes linear time in the number of tasks
Space O(1) Frequency array or Counter has fixed size (26) regardless of input

The time complexity is linear because each task is visited once. The space complexity is effectively constant because the task set is limited to 26 letters.

Test Cases

# Basic examples
assert Solution().leastInterval(["A","A","A","B","B","B"], 2) == 8
assert Solution().leastInterval(["A","C","A","B","D","B"], 1) == 6
assert Solution().leastInterval(["A","A","A","B","B","B"], 3) == 10

# Edge cases
assert Solution().leastInterval(["A"], 0) == 1  # Single task, no cooling
assert Solution().leastInterval(["A","A","A","A"], 0) == 4  # No cooling, repeated tasks
assert Solution().leastInterval(["A","A","A","B","B","B","C","C"], 2) == 8  # Multiple tasks, some less frequent

# Max cooling
assert Solution().leastInterval(["A","B","C","D"], 100) == 4  # Cooling larger than tasks, no idles needed if all tasks different
Test Why
["A","A","A","B","B","B"], 2 Standard case with repeated tasks and cooling
["A","C","A","B","D","B"], 1 Tasks can fill cooling periods
["A","A","A","B","B","B"], 3 Cooling longer than number of other tasks, requires idles
["A"], 0 Single task, no cooling
["A","A","A","A"], 0 Repeated tasks but no cooling, sequential execution
["A","A","A","B","B","B","C","C"], 2 Mix of frequencies filling cooling periods
["A","B","C","D"], 100 Cooling larger than number of unique tasks, no idles required

Edge Cases

  1. No Cooling (n=0): If n is 0, no idle intervals are needed. The CPU can process tasks back-to-back. The implementation handles this upfront to avoid unnecessary calculations.
  2. Single Task Repeated Many Times: When one task is repeated many times, the algorithm correctly calculates the necessary idle intervals using the (f_max-1)*(n+1) formula. It ensures that the task is spaced correctly