Task Scheduler

Find the minimum number of intervals the CPU will take to finish all given tasks with a cooldown period between identical tasks

Language Selection

Choose your preferred programming language

Showing: Python

Task Scheduler

Problem Statement

You are given an array of CPU tasks, each represented by a character from A to Z, and a non-negative integer n representing the cooldown period between two identical tasks. In each unit of time the CPU can either complete a task or remain idle.

Return the minimum number of units of time the CPU will take to finish all the given tasks.

Constraints:

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

Examples:

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: With no cooldown, tasks can be executed back-to-back: A -> B -> A -> B -> A -> B.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Approach 1: Sorting-Based Greedy

Algorithm:

  1. Count the frequency of each task
  2. In each round of length n + 1, pick tasks in descending frequency order
  3. After each round, re-sort the remaining frequencies
  4. The last round may be shorter than n + 1 (no idle padding needed)

Time Complexity: O(n * 26 log 26) which simplifies to O(n) since 26 is constant Space Complexity: O(1) (frequency array of fixed size 26)

Python:

def leastInterval(tasks, n):
    """
    Task scheduler using sorting-based greedy strategy
    Time: O(n)
    Space: O(1)
    """
    freq = [0] * 26
    for task in tasks:
        freq[ord(task) - ord('A')] += 1

    freq.sort(reverse=True)
    time = 0

    while freq[0] > 0:
        # Process one cycle of length n+1
        count = 0
        for i in range(min(26, n + 1)):
            if freq[i] > 0:
                freq[i] -= 1
                count += 1

        # If tasks remain, this was a full cycle (with possible idle)
        # If no tasks remain, only count actual tasks in last cycle
        if freq[0] > 0:
            time += n + 1
        else:
            time += count

        freq.sort(reverse=True)

    return time

Java:

import java.util.Arrays;

class Solution {
    /**
     * Task scheduler using sorting-based greedy strategy
     * Time: O(n)
     * Space: O(1)
     */
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char task : tasks) {
            freq[task - 'A']++;
        }

        Arrays.sort(freq);
        int time = 0;

        while (freq[25] > 0) {
            int count = 0;
            for (int i = 25; i >= Math.max(0, 26 - (n + 1)); i--) {
                if (freq[i] > 0) {
                    freq[i]--;
                    count++;
                }
            }

            if (freq[25] > 0) {
                time += n + 1;
            } else {
                // Check if any tasks remain after re-sort
                Arrays.sort(freq);
                if (freq[25] > 0) {
                    time += n + 1;
                } else {
                    time += count;
                }
                continue;
            }

            Arrays.sort(freq);
        }

        return time;
    }
}

Go:

import "sort"

// leastInterval - Task scheduler using sorting-based greedy
// Time: O(n)
// Space: O(1)
func leastInterval(tasks []byte, n int) int {
    freq := make([]int, 26)
    for _, task := range tasks {
        freq[task-'A']++
    }

    sort.Sort(sort.Reverse(sort.IntSlice(freq)))
    time := 0

    for freq[0] > 0 {
        count := 0
        limit := n + 1
        if limit > 26 {
            limit = 26
        }
        for i := 0; i < limit; i++ {
            if freq[i] > 0 {
                freq[i]--
                count++
            }
        }

        if freq[0] > 0 {
            time += n + 1
        } else {
            // Re-check after sort
            sort.Sort(sort.Reverse(sort.IntSlice(freq)))
            if freq[0] > 0 {
                time += n + 1
            } else {
                time += count
            }
            continue
        }

        sort.Sort(sort.Reverse(sort.IntSlice(freq)))
    }

    return time
}

JavaScript:

/**
 * Task scheduler using sorting-based greedy strategy
 * Time: O(n)
 * Space: O(1)
 */
function leastInterval(tasks, n) {
    const freq = new Array(26).fill(0);
    for (const task of tasks) {
        freq[task.charCodeAt(0) - 65]++;
    }

    freq.sort((a, b) => b - a);
    let time = 0;

    while (freq[0] > 0) {
        let count = 0;
        for (let i = 0; i < Math.min(26, n + 1); i++) {
            if (freq[i] > 0) {
                freq[i]--;
                count++;
            }
        }

        freq.sort((a, b) => b - a);

        if (freq[0] > 0) {
            time += n + 1;
        } else {
            time += count;
        }
    }

    return time;
}

C#:

using System;

public class Solution {
    /// <summary>
    /// Task scheduler using sorting-based greedy strategy
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int LeastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        foreach (char task in tasks) {
            freq[task - 'A']++;
        }

        Array.Sort(freq);
        Array.Reverse(freq);
        int time = 0;

        while (freq[0] > 0) {
            int count = 0;
            for (int i = 0; i < Math.Min(26, n + 1); i++) {
                if (freq[i] > 0) {
                    freq[i]--;
                    count++;
                }
            }

            Array.Sort(freq);
            Array.Reverse(freq);

            if (freq[0] > 0) {
                time += n + 1;
            } else {
                time += count;
            }
        }

        return time;
    }
}

Approach 2: Math Formula (Optimal)

Algorithm:

  1. Count the frequency of each task
  2. Find the maximum frequency maxFreq
  3. Count how many tasks share this maximum frequency (maxCount)
  4. The answer is max(totalTasks, (maxFreq - 1) * (n + 1) + maxCount)

Intuition: The most frequent task creates a frame of maxFreq - 1 gaps, each of width n + 1. The last row holds only the tasks that share the maximum frequency. If all tasks fit into the frame (or we have enough variety to fill gaps), the total is just the number of tasks.

Time Complexity: O(n) for counting frequencies Space Complexity: O(1) (fixed-size frequency array)

Python:

def leastInterval(tasks, n):
    """
    Task scheduler using mathematical formula
    Time: O(n)
    Space: O(1)
    """
    freq = [0] * 26
    for task in tasks:
        freq[ord(task) - ord('A')] += 1

    max_freq = max(freq)
    max_count = freq.count(max_freq)

    # Frame created by most frequent task:
    # (maxFreq - 1) full rows of (n + 1) slots + last row of maxCount tasks
    result = (max_freq - 1) * (n + 1) + max_count

    # If we have enough tasks to fill all idle slots, answer is just len(tasks)
    return max(len(tasks), result)

Java:

class Solution {
    /**
     * Task scheduler using mathematical formula
     * Time: O(n)
     * Space: O(1)
     */
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char task : tasks) {
            freq[task - 'A']++;
        }

        int maxFreq = 0;
        for (int f : freq) {
            maxFreq = Math.max(maxFreq, f);
        }

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

        // Frame: (maxFreq - 1) rows of (n + 1) width + last row of maxCount
        int result = (maxFreq - 1) * (n + 1) + maxCount;

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

Go:

// leastInterval - Task scheduler using math formula
// Time: O(n)
// Space: O(1)
func leastInterval(tasks []byte, n int) int {
    freq := make([]int, 26)
    for _, task := range tasks {
        freq[task-'A']++
    }

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

    maxCount := 0
    for _, f := range freq {
        if f == maxFreq {
            maxCount++
        }
    }

    // Frame: (maxFreq - 1) rows of (n + 1) width + last row of maxCount
    result := (maxFreq-1)*(n+1) + maxCount

    if len(tasks) > result {
        return len(tasks)
    }
    return result
}

JavaScript:

/**
 * Task scheduler using mathematical formula
 * Time: O(n)
 * Space: O(1)
 */
function leastInterval(tasks, n) {
    const freq = new Array(26).fill(0);
    for (const task of tasks) {
        freq[task.charCodeAt(0) - 65]++;
    }

    const maxFreq = Math.max(...freq);
    let maxCount = 0;
    for (const f of freq) {
        if (f === maxFreq) {
            maxCount++;
        }
    }

    // Frame: (maxFreq - 1) rows of (n + 1) width + last row of maxCount
    const result = (maxFreq - 1) * (n + 1) + maxCount;

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

C#:

using System;
using System.Linq;

public class Solution {
    /// <summary>
    /// Task scheduler using mathematical formula
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int LeastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        foreach (char task in tasks) {
            freq[task - 'A']++;
        }

        int maxFreq = freq.Max();
        int maxCount = freq.Count(f => f == maxFreq);

        // Frame: (maxFreq - 1) rows of (n + 1) width + last row of maxCount
        int result = (maxFreq - 1) * (n + 1) + maxCount;

        return Math.Max(tasks.Length, result);
    }
}

Key Insights

  1. Frame Visualization: The most frequent task creates a “frame” of time slots. Picture a grid where each row is n + 1 wide and there are maxFreq rows. Other tasks fill into the gaps.

  2. Idle Slots Absorb Tasks: Less frequent tasks fill idle slots between occurrences of the most frequent task, reducing wasted time.

  3. Two Cases: Either idle time exists (answer is the frame size) or enough tasks fill all gaps (answer is just the total number of tasks).

  4. Why max() Matters: When there are many distinct tasks, they fill all idle slots and the total time equals the task count. The formula handles this with max(len(tasks), frame_size).

  5. Constant Space: Since tasks are uppercase letters only (26 possible values), the frequency array is constant size.

Edge Cases

  • Cooldown is 0: n = 0 → answer is simply len(tasks) since no idle time is needed
  • Single task type: ["A","A","A"], n = 2 → answer is 7 (A idle idle A idle idle A)
  • All unique tasks: ["A","B","C","D"], n = 2 → answer is 4 (no idle needed)
  • Single task: ["A"], n = 5 → answer is 1
  • All tasks same frequency: ["A","A","B","B","C","C"], n = 2 → answer is 6

Test Cases

# Test case 1: Standard case with idle slots
assert leastInterval(["A","A","A","B","B","B"], 2) == 8

# Test case 2: No cooldown needed
assert leastInterval(["A","A","A","B","B","B"], 0) == 6

# Test case 3: Many idle slots needed
assert leastInterval(["A","A","A","A","A","A","B","C","D","E","F","G"], 2) == 16

# Test case 4: Single task type
assert leastInterval(["A","A","A"], 2) == 7

# Test case 5: All different tasks
assert leastInterval(["A","B","C","D"], 2) == 4

# Test case 6: Single task
assert leastInterval(["A"], 100) == 1

# Test case 7: Two tasks, large cooldown
assert leastInterval(["A","A","B","B"], 3) == 6

Common Mistakes

  1. Using n instead of n + 1 for cycle length: Each cycle includes the task itself plus n cooldown slots, totaling n + 1 units.

  2. Forgetting the max(totalTasks, formula) check: When many distinct tasks exist, idle slots are fully absorbed and the answer is just the total task count.

  3. Incorrect maxCount calculation: Failing to count all tasks that share the maximum frequency leads to an undercount in the last row.

  4. Not handling n = 0: When cooldown is 0, the answer is always the total number of tasks regardless of frequency distribution.

  5. Overcomplicating with simulation: The math formula approach is simpler and avoids simulation pitfalls with heap management or sorting order.