Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Task Scheduler

MEDIUMProblemSolveExternal Links

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.

Examples

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. There is enough task variety to fill all slots without any idle time.

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.

Constraints

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

Editorial

Brute Force

Intuition

The most direct way to solve this problem is to simulate the CPU one interval at a time. At each time step, we look at all remaining tasks and pick the one that:

  1. Is not in cooldown — it wasn't executed in the last n intervals
  2. Has the highest remaining count — a greedy choice to reduce future scheduling pressure

If no task satisfies condition 1, the CPU idles for that interval.

This greedy simulation works because always picking the most frequent available task maximizes utilization of each slot and minimizes the total idle time. We continue until all task counts reach zero.

Step-by-Step

Let's trace through tasks = ["A","A","A","B","B","B"], n = 2:

Setup: Count frequencies: A=3, B=3. Maintain a processed list to track which tasks were executed and when.

Cycle 1: Both A(3) and B(3) are available (no cooldown active). Pick A (highest count, tie-break by order). Execute A. Remaining: A=2, B=3.

Cycle 2: A was executed 1 cycle ago (need gap of 2) — in cooldown. B(3) is available. Execute B. Remaining: A=2, B=2.

Cycle 3: Check last 2 processed: [A, B]. A appears → cooldown. B appears → cooldown. No task available → IDLE.

Cycle 4: Check last 2 processed: [B, idle]. A not found → available! B found → cooldown. Execute A. Remaining: A=1, B=2.

Cycle 5: Check last 2 processed: [idle, A]. B not found → available! A found → cooldown. Execute B. Remaining: A=1, B=1.

Cycle 6: Check last 2 processed: [A, B]. Both in cooldown. IDLE.

Cycle 7: Check last 2 processed: [B, idle]. A available. Execute A. Remaining: A=0, B=1.

Cycle 8: Check last 2 processed: [idle, A]. B available. Execute B. Remaining: A=0, B=0. Done!

Result: 8 intervals. Schedule: A → B → idle → A → B → idle → A → B.

Code

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int count[26] = {0};
        for (char t : tasks) count[t - 'A']++;

        vector<pair<int,int>> arr;
        for (int i = 0; i < 26; i++)
            if (count[i] > 0)
                arr.push_back({count[i], i});

        int time = 0;
        vector<int> processed;
        while (!arr.empty()) {
            int best = -1;
            for (int i = 0; i < (int)arr.size(); i++) {
                bool ok = true;
                for (int j = max(0, time - n); j < time; j++) {
                    if (processed[j] == arr[i].second) {
                        ok = false;
                        break;
                    }
                }
                if (ok && (best == -1 ||
                    arr[best].first < arr[i].first))
                    best = i;
            }
            time++;
            if (best != -1) {
                processed.push_back(arr[best].second);
                arr[best].first--;
                if (arr[best].first == 0)
                    arr.erase(arr.begin() + best);
            } else {
                processed.push_back(-1);
            }
        }
        return time;
    }
};
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = [0] * 26
        for t in tasks:
            count[ord(t) - ord('A')] += 1

        arr = []
        for i in range(26):
            if count[i] > 0:
                arr.append([count[i], i])

        time = 0
        processed = []
        while arr:
            best = -1
            for i in range(len(arr)):
                ok = all(
                    processed[j] != arr[i][1]
                    for j in range(max(0, time - n), time)
                )
                if ok and (best == -1 or
                           arr[best][0] < arr[i][0]):
                    best = i

            time += 1
            if best != -1:
                processed.append(arr[best][1])
                arr[best][0] -= 1
                if arr[best][0] == 0:
                    arr.pop(best)
            else:
                processed.append(-1)

        return time
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) count[t - 'A']++;

        List<int[]> arr = new ArrayList<>();
        for (int i = 0; i < 26; i++)
            if (count[i] > 0)
                arr.add(new int[]{count[i], i});

        int time = 0;
        List<Integer> processed = new ArrayList<>();
        while (!arr.isEmpty()) {
            int best = -1;
            for (int i = 0; i < arr.size(); i++) {
                boolean ok = true;
                for (int j = Math.max(0, time - n); j < time; j++) {
                    if (processed.get(j) == arr.get(i)[1]) {
                        ok = false;
                        break;
                    }
                }
                if (ok && (best == -1 ||
                    arr.get(best)[0] < arr.get(i)[0]))
                    best = i;
            }
            time++;
            if (best != -1) {
                processed.add(arr.get(best)[1]);
                arr.get(best)[0]--;
                if (arr.get(best)[0] == 0)
                    arr.remove(best);
            } else {
                processed.add(-1);
            }
        }
        return time;
    }
}

Complexity

Time Complexity: O(t × n) where t is the total number of intervals (including idle time) and n is the cooldown period. At each interval, we check the last n processed entries for each remaining task type.

Space Complexity: O(t) to store the processed list of all executed tasks and idle slots.

Why This Approach Is Not Efficient

The brute force simulation has significant inefficiencies:

  1. Redundant cooldown scanning: At each interval, we scan the last n processed entries for every remaining task type. This is O(n) work per task per interval, repeated across all t intervals.

  2. Cannot skip idle time: When all tasks are in cooldown, the simulation must process each idle interval one by one, even though consecutive idle slots are predictable.

  3. Linear task selection: Finding the highest-count available task requires scanning all remaining tasks every interval, rather than maintaining a sorted structure.

For inputs with large cooldown periods and many repeated tasks, the total time t can be much larger than the number of tasks, making O(t × n) impractical.

Can we do better? Instead of scanning tasks linearly each interval, we can use a max-heap (priority queue) to always retrieve the highest-frequency task in O(1), and a FIFO queue to efficiently manage cooldowns — eliminating the need to scan the processed history.

Better Approach - Max-Heap with Cooldown Queue

Intuition

The brute force scans all tasks and their cooldown history at every interval. We can dramatically improve this by using two data structures:

  1. Max-Heap: Stores task frequencies. The highest-frequency task is always at the top — ready to be selected in O(1).

  2. Cooldown Queue (FIFO): Stores pairs (remaining_count, available_at_time). When a task is executed, it enters the cooldown queue with the time when it becomes available again.

Why always pick the most frequent task? The most frequent task is the hardest to schedule — it needs the most slots with cooldown gaps between them. By always executing it first when available, we minimize future scheduling conflicts and reduce idle time.

The workflow:

  • Pop the most frequent task from the heap and execute it.
  • Decrease its count and push it to the cooldown queue with available_time = current_time + n.
  • When a task's cooldown expires, push it back into the heap.
  • If the heap is empty but tasks are cooling down, fast-forward time to the next available task — no need to simulate idle slots one by one.

Step-by-Step

Let's trace through tasks = ["A","A","A","B","B","B"], n = 2:

Setup: Frequencies: A=3, B=3. Max-heap: [3, 3]. Cooldown queue: empty. Time = 0.

Time 1: Pop max (3) from heap → execute task A. Count → 2. Push (2, avail@3) to cooldown. Heap: [3].

Time 2: Pop max (3) → execute task B. Count → 2. Push (2, avail@4). Heap: []. Cooldown: [(2,@3), (2,@4)].

Time 3: Heap empty → IDLE. Check cooldown front: (2, @3) — available at time 3! Push count 2 back to heap. Heap: [2]. Cooldown: [(2,@4)].

Time 4: Pop max (2) → execute task A. Count → 1. Push (1, avail@6). Check cooldown: (2, @4) — available! Push back. Heap: [2].

Time 5: Pop max (2) → execute task B. Count → 1. Push (1, avail@7). Heap: []. Cooldown: [(1,@6), (1,@7)].

Time 6: Heap empty → IDLE. Cooldown front: (1, @6) — available! Push back. Heap: [1].

Time 7: Pop (1) → execute A. Count → 0, task complete! Cooldown: (1, @7) — available! Push back. Heap: [1].

Time 8: Pop (1) → execute B. Count → 0, complete! Heap empty, cooldown empty. Done!

Result: 8 intervals. Schedule: A → B → idle → A → B → idle → A → B.

Build max-heap from task frequencies — Build max-heap from task frequencies. A=3 and B=3 are the two distinct tasks.

Code

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> count;
        for (char t : tasks) count[t]++;

        priority_queue<int> maxHeap;
        for (auto& [ch, cnt] : count)
            maxHeap.push(cnt);

        int time = 0;
        queue<pair<int,int>> q;
        while (!maxHeap.empty() || !q.empty()) {
            time++;
            if (maxHeap.empty()) {
                time = q.front().second;
            } else {
                int cnt = maxHeap.top() - 1;
                maxHeap.pop();
                if (cnt > 0)
                    q.push({cnt, time + n});
            }
            if (!q.empty() && q.front().second == time) {
                maxHeap.push(q.front().first);
                q.pop();
            }
        }
        return time;
    }
};
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        time = 0
        q = deque()  # pairs of [-count, available_time]
        while maxHeap or q:
            time += 1
            if not maxHeap:
                time = q[0][1]
            else:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    q.append([cnt, time + n])
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])

        return time
class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> count = new HashMap<>();
        for (char t : tasks)
            count.merge(t, 1, Integer::sum);

        PriorityQueue<Integer> maxHeap =
            new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(count.values());

        int time = 0;
        Queue<int[]> q = new LinkedList<>();
        while (!maxHeap.isEmpty() || !q.isEmpty()) {
            time++;
            if (maxHeap.isEmpty()) {
                time = q.peek()[1];
            } else {
                int cnt = maxHeap.poll() - 1;
                if (cnt > 0)
                    q.add(new int[]{cnt, time + n});
            }
            if (!q.isEmpty() && q.peek()[1] == time) {
                maxHeap.add(q.poll()[0]);
            }
        }
        return time;
    }
}

Complexity

Time Complexity: O(m) where m is the total number of tasks. Each task is pushed to and popped from the heap at most once. Heap operations are O(log 26) = O(1) since there are at most 26 distinct task types. The fast-forward optimization skips consecutive idle slots.

Space Complexity: O(1) — the heap and cooldown queue each hold at most 26 entries (one per distinct task character), which is constant regardless of input size.

Why This Approach Is Not Efficient

While the max-heap approach achieves O(m) time complexity, it has notable drawbacks:

  1. Implementation complexity: Managing a max-heap plus a FIFO cooldown queue with precise timing requires careful coordination. Off-by-one errors in cooldown tracking (time + n vs time + n + 1) are a common pitfall.

  2. Still simulates the process: Even with fast-forwarding idle slots, we process each task execution individually through push/pop operations on the heap and queue.

  3. Unnecessary for this problem: The scheduling structure is actually predictable from the frequency distribution alone — we don't need to simulate the process at all.

Key insight: The task with the highest frequency creates a fixed "frame" structure for the schedule. We need (maxf - 1) blocks of (n + 1) slots to space out the most frequent task, plus a final block for all tasks sharing that maximum frequency. Can we compute this directly with a mathematical formula instead of simulating?

Optimal Approach - Mathematical Formula

Intuition

Instead of simulating the schedule, we can compute the answer directly using a mathematical formula based on the most frequent task.

Key insight: The task with the highest frequency (maxf) determines the minimum structure of the schedule. If a task appears maxf times, these copies must be at least n intervals apart, creating (maxf - 1) "blocks" of size (n + 1):

Block 1: [Task, _, _, ..., _]  ← (n+1) slots
Block 2: [Task, _, _, ..., _]  ← (n+1) slots
  ...
Block (maxf-1): [Task, _, ..., _]
Final:   [Tasks with max freq]  ← maxCount slots

The total from this structure is: (maxf - 1) × (n + 1) + maxCount

where maxCount is the number of distinct tasks sharing the maximum frequency.

But what if we have many diverse tasks? If there are enough different tasks to fill all idle slots, the total time is simply len(tasks) — no idle intervals needed at all.

The final answer combines both cases:

answer = max(len(tasks), (maxf - 1) × (n + 1) + maxCount)

Step-by-Step

Let's trace through tasks = ["A","A","A","B","B","B"], n = 2:

Step 1 — Count Frequencies:
A appears 3 times, B appears 3 times. Frequency array: [3, 3, 0, ..., 0].

Step 2 — Find Maximum Frequency:
maxf = 3. The most frequent task(s) create the scheduling bottleneck.

Step 3 — Count Tasks with Maximum Frequency:
Both A and B have frequency 3, so maxCount = 2.

Step 4 — Visualize the Block Structure:

Block 1: [A, B, idle]  ← (n+1) = 3 slots
Block 2: [A, B, idle]  ← (n+1) = 3 slots
Final:   [A, B]        ← maxCount = 2 slots

We need (maxf - 1) = 2 complete blocks, each of size (n + 1) = 3.

Step 5 — Apply the Formula:
(maxf - 1) × (n + 1) + maxCount = (3 - 1) × (2 + 1) + 2 = 6 + 2 = 8

Step 6 — Compare with Total Tasks:
max(len(tasks), formula) = max(6, 8) = 8

The formula gives 8 because we need 2 idle slots that can't be filled with other tasks.

Edge Case — When len(tasks) Dominates:
Consider tasks = [A, C, A, B, D, B], n = 1: maxf=2, maxCount=2.
Formula: (2-1) × (1+1) + 2 = 4. But len(tasks) = 6.
Schedule: A → B → C → D → A → B — no idle needed!
Answer: max(6, 4) = 6. Enough task variety eliminates all idle time.

Result: For the original input, minimum intervals = 8.

Start with input tasks array — Start with input tasks array. Goal: find minimum CPU intervals with cooldown n=2.

Code

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int count[26] = {0};
        for (char t : tasks) count[t - 'A']++;

        int maxf = *max_element(count, count + 26);
        int maxCount = 0;
        for (int c : count)
            if (c == maxf) maxCount++;

        int time = (maxf - 1) * (n + 1) + maxCount;
        return max((int)tasks.size(), time);
    }
};
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = [0] * 26
        for t in tasks:
            count[ord(t) - ord('A')] += 1

        maxf = max(count)
        maxCount = count.count(maxf)

        time = (maxf - 1) * (n + 1) + maxCount
        return max(len(tasks), time)
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) count[t - 'A']++;

        int maxf = 0;
        for (int c : count) maxf = Math.max(maxf, c);

        int maxCount = 0;
        for (int c : count)
            if (c == maxf) maxCount++;

        int time = (maxf - 1) * (n + 1) + maxCount;
        return Math.max(tasks.length, time);
    }
}

Complexity

Time Complexity: O(m) where m is the total number of tasks. We iterate through the tasks once to count frequencies, then scan the 26-element frequency array to find maxf and maxCount. Since 26 is a constant, this simplifies to O(m).

Space Complexity: O(1) — we use a fixed-size frequency array of 26 elements regardless of input size.