Task Scheduler

Medium Problem 83 of 151 Java and Python

Problem

You are given an array of CPU tasks, each a letter A–Z, and a cooldown n. Each interval the CPU either runs one task or stays idle. Two runs of the same task must be at least n intervals apart.

Return the minimum number of intervals needed to run all tasks.

Example 1

Input: tasks = ["A", "A", "A", "B", "B", "B"], n = 2
Output: 8
Why: A B idle A B idle A B.

Example 2

Input: tasks = ["A", "C", "A", "B", "D", "B"], n = 1
Output: 6
Why: A B A B C D: no idle needed.

Example 3

Input: tasks = ["A", "A", "A", "B", "B", "B"], n = 3
Output: 10
Why: A B idle idle A B idle idle A B.

Constraints

1 ≤ tasks.length ≤ 10⁴
0 ≤ n ≤ 100

Explanation

The most frequent task is the bottleneck. If it appears maxCount times, it splits the timeline into maxCount - 1 gaps of length n + 1, plus a final slot shared by every task that also has the maximum count.

That gives (maxCount - 1) × (n + 1) + tiedForMax intervals. If there are so many different tasks that no idling is needed, the answer is simply tasks.length, so take the larger of the two.

Approach 1 · Better

Simulate with a max-heap and a cooldown queue

Time O(T · log 26), T = total intervals
Space O(26)

Each interval, run the task with the most remaining copies that is not cooling down. Cooling tasks wait in a queue with the time they become available.

Push every task count into a max-heap.
Each tick: if the heap is non-empty, pop a count, decrement it, and if it is still positive queue it with ready time time + n.
Move tasks whose ready time has come from the queue back into the heap. Stop when both are empty.

Java

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char task : tasks) {
            count[task - 'A']++;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : count) {
            if (c > 0) {
                heap.offer(c);
            }
        }
        Deque<int[]> cooling = new ArrayDeque<>(); // { remaining, readyTime }
        int time = 0;
        while (!heap.isEmpty() || !cooling.isEmpty()) {
            time++;
            if (!heap.isEmpty()) {
                int remaining = heap.poll() - 1;
                if (remaining > 0) {
                    cooling.add(new int[] { remaining, time + n });
                }
            }
            if (!cooling.isEmpty() && cooling.peek()[1] == time) {
                heap.offer(cooling.poll()[0]);
            }
        }
        return time;
    }
}

Python

import heapq
from collections import Counter, deque

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        heap = [-c for c in Counter(tasks).values()]
        heapq.heapify(heap)
        cooling = deque()  # (remaining, ready_time)
        time = 0
        while heap or cooling:
            time += 1
            if heap:
                remaining = -heapq.heappop(heap) - 1
                if remaining:
                    cooling.append((remaining, time + n))
            if cooling and cooling[0][1] == time:
                heapq.heappush(heap, -cooling.popleft()[0])
        return time

Approach 2 · Optimal

Counting formula

Time O(T), T = number of tasks
Space O(26)

Build the schedule around the most frequent task: (maxCount - 1) × (n + 1) + tiedForMax, but never less than the number of tasks.

Count each task; let maxCount be the highest count and tied the number of tasks with that count.
Return max(tasks.length, (maxCount - 1) * (n + 1) + tied).

Java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        int maxCount = 0;
        for (char task : tasks) {
            maxCount = Math.max(maxCount, ++count[task - 'A']);
        }
        int tied = 0;
        for (int c : count) {
            if (c == maxCount) {
                tied++;
            }
        }
        return Math.max(tasks.length, (maxCount - 1) * (n + 1) + tied);
    }
}

Python

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks).values()
        max_count = max(counts)
        tied = sum(1 for c in counts if c == max_count)
        return max(len(tasks), (max_count - 1) * (n + 1) + tied)

Complexity compared

Approach	Time	Space
Better Simulate with a max-heap and a cooldown queue	O(T · log 26), T = total intervals	O(26)
Optimal Counting formula	O(T), T = number of tasks	O(26)

Key takeaways

Explain the formula with a picture: rows of length n + 1, one per occurrence of the most frequent task.
The simulation generalises when tasks have different cooldowns; the formula does not.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem