Task Scheduler

A CPU has a list of tasks to run. Same task cannot run twice in a row without a cooldown gap. You want the least total time to finish them all. The trick is to always run the task that is left the most. That keeps the CPU busy and cuts down waiting. A heap makes picking that task easy.

🎯 The Problem

You get tasks for a CPU, and you want them done in the least time. Here are the rules.

• Each task is a letter like A or B.
• A number n is the cooldown. After running a task, wait at least n slots before running it again.
• Each slot is one unit of time. A slot either runs a task or sits idle.
• You want the smallest total number of slots to run every task.

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

Explanation:
One valid order: A B idle A B idle A B
That is 8 slots. Each A is at least 2 slots apart, same for B.

So the most frequent task forces gaps. We must fill those gaps with other tasks or with idle time.

Here is the idea drawn as a timeline. The most frequent task A sets the frame, and gaps get filled.

🐢 Approach 1: Simulate Every Slot (Brute Force)

The idea in one line: step through time slot by slot and run the best ready task.

The idea:

• Walk time one slot at a time.
• Each slot, run the task with the most copies left that is not on cooldown.
• Track a cooldown for every task. Count every slot, idle ones too.

How it works:

• It mirrors the real process exactly.
• It does give the right answer.

Why it is weak:

• Tracking cooldowns and scanning for the best task each slot is fiddly.
• Scanning all task types every slot is slow.
• The total slot count can be large.

Here is the slot-by-slot simulation:

from collections import Counter


def least_interval(tasks, n):
    counts = Counter(tasks)
    cooldown = {}
    time = 0

    while counts:
        time += 1
        available = [task for task in counts if cooldown.get(task, 0) <= time]
        if available:
            task = max(available, key=lambda item: counts[item])
            counts[task] -= 1
            cooldown[task] = time + n + 1
            if counts[task] == 0:
                del counts[task]
    return time

⚡ Approach 2: Greedy With a Max-Heap (Best)

The idea in one line: run the task with the most copies left, in rounds of n + 1 slots.

The idea:

• Each step, run the task with the most copies left.
• The busiest task first keeps the CPU full and cuts idle time.

What the heap gives us:

• A max-heap keeps the largest value at the top. A binary tree means each node has at most two children.
• Reading the top is instant. Adding or removing is O(log n). It is also called a priority queue.

How one round works:

• Count each task. Put the counts into a max-heap.
• Each round covers n + 1 slots, the spacing one task needs.
• Pop up to n + 1 tasks. Run each once, lowering its count by one.
• Hold the still-positive counts aside, then push them back after the round.

How it counts time:

• A full round adds n + 1 to the time, including any idle slots.
• The last round adds only the tasks actually run.
• Stop when the heap is empty and nothing is held.

Here is the max-heap simulation:

from collections import Counter, deque
import heapq


def least_interval(tasks, n):
    heap = [-count for count in Counter(tasks).values()]
    heapq.heapify(heap)
    wait = deque()
    time = 0

    while heap or wait:
        time += 1
        if heap:
            count = heapq.heappop(heap) + 1
            if count:
                wait.append((time + n, count))
        if wait and wait[0][0] == time:
            heapq.heappush(heap, wait.popleft()[1])
    return time

🧮 Approach 3: Math Formula (Alternative)

The idea in one line: the busiest task fixes the schedule shape, so compute the answer directly.

The idea:

• The most frequent task, with count maxCount, creates maxCount - 1 gaps.
• Each gap is n + 1 wide.
• Add the number of tasks tied for that top count.

How it works:

• The formula is (maxCount - 1) · (n + 1) + (tasks tied for top).
• The answer is the larger of that formula and the total number of tasks.

Why it is neat:

• No heap. Just read the counts.
• It runs in O(total tasks) time and O(1) extra space.

Here is the count max-heap drawn as a tree for the example. Both A and B have count 3, so one sits on top.

Steps to Solve

1. Count how many times each task appears.
2. Put all counts into a max-heap, so the largest count is on top.
3. In each round, pop up to n + 1 tasks and lower each count by one.
4. Keep the still-positive counts aside, then push them back after the round.
5. Add n + 1 to the time for a full round, or just the tasks run in the last round.
6. Stop when the heap is empty.

#include <stdio.h>
#include <string.h>

int leastInterval(char tasks[], int len, int n) {
    int counts[26] = {0};
    for (int i = 0; i < len; i++) counts[tasks[i] - 'A']++;

    int maxCount = 0;
    for (int i = 0; i < 26; i++) if (counts[i] > maxCount) maxCount = counts[i];

    int maxGroups = 0;  // how many tasks share the top count
    for (int i = 0; i < 26; i++) if (counts[i] == maxCount) maxGroups++;

    // (maxCount - 1) gaps of size (n + 1), plus the final tied tasks
    int byFormula = (maxCount - 1) * (n + 1) + maxGroups;
    return byFormula > len ? byFormula : len;  // never less than total tasks
}

int main(void) {
    char tasks[] = {'A', 'A', 'A', 'B', 'B', 'B'};
    printf("%d\n", leastInterval(tasks, 6, 2));
    return 0;
}

8

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

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

    priority_queue<int> heap;            // max-heap of counts
    for (auto& p : freq) heap.push(p.second);

    int time = 0;
    while (!heap.empty()) {
        vector<int> hold;
        int run = 0;
        for (int i = 0; i < n + 1; i++) {  // one round covers n+1 slots
            if (!heap.empty()) {
                int c = heap.top(); heap.pop();
                if (c - 1 > 0) hold.push_back(c - 1);
                run++;
            }
        }
        for (int c : hold) heap.push(c);   // push the leftovers back
        time += heap.empty() ? run : n + 1; // full round or last partial round
    }
    return time;
}

int main() {
    vector<char> tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
    cout << leastInterval(tasks, 2) << endl;
    return 0;
}

8

import java.util.PriorityQueue;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

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

        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.addAll(freq.values());        // max-heap of counts

        int time = 0;
        while (!heap.isEmpty()) {
            List<Integer> hold = new ArrayList<>();
            int run = 0;
            for (int i = 0; i < n + 1; i++) {   // one round covers n+1 slots
                if (!heap.isEmpty()) {
                    int c = heap.poll();
                    if (c - 1 > 0) hold.add(c - 1);
                    run++;
                }
            }
            for (int c : hold) heap.offer(c);   // push leftovers back
            time += heap.isEmpty() ? run : n + 1;
        }
        return time;
    }

    public static void main(String[] args) {
        char[] tasks = { 'A', 'A', 'A', 'B', 'B', 'B' };
        System.out.println(leastInterval(tasks, 2));
    }
}

8

import heapq
from collections import Counter


def least_interval(tasks, n):
    freq = Counter(tasks)                    # count each task
    heap = [-c for c in freq.values()]       # negate for a max-heap
    heapq.heapify(heap)

    time = 0
    while heap:
        hold = []
        run = 0
        for _ in range(n + 1):               # one round covers n+1 slots
            if heap:
                c = -heapq.heappop(heap)      # largest count
                if c - 1 > 0:
                    hold.append(-(c - 1))     # keep the leftover, negated
                run += 1
        for c in hold:
            heapq.heappush(heap, c)           # push leftovers back
        time += run if not heap else n + 1    # last round vs full round

    return time


tasks = ["A", "A", "A", "B", "B", "B"]
print(least_interval(tasks, 2))

8

class MaxHeap {
  constructor() { this.data = []; }
  size() { return this.data.length; }
  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {                       // bubble up
      const parent = (i - 1) >> 1;
      if (this.data[i] > this.data[parent]) {
        [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
        i = parent;
      } else break;
    }
  }
  pop() {
    const result = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      while (true) {                      // bubble down
        let left = 2 * i + 1, right = 2 * i + 2, largest = i;
        if (left < this.data.length && this.data[left] > this.data[largest]) largest = left;
        if (right < this.data.length && this.data[right] > this.data[largest]) largest = right;
        if (largest === i) break;
        [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
        i = largest;
      }
    }
    return result;
  }
}

function leastInterval(tasks, n) {
  const freq = {};
  for (const t of tasks) freq[t] = (freq[t] || 0) + 1;

  const heap = new MaxHeap();
  for (const c of Object.values(freq)) heap.push(c);

  let time = 0;
  while (heap.size()) {
    const hold = [];
    let run = 0;
    for (let i = 0; i < n + 1; i++) {    // one round covers n+1 slots
      if (heap.size()) {
        const c = heap.pop();
        if (c - 1 > 0) hold.push(c - 1);
        run++;
      }
    }
    for (const c of hold) heap.push(c);  // push leftovers back
    time += heap.size() ? n + 1 : run;
  }
  return time;
}

console.log(leastInterval(["A", "A", "A", "B", "B", "B"], 2));

8

Let us walk through the Python version line by line. The greedy rounds with a max-heap drive the whole thing.

The first line uses Counter to count each task. So ["A","A","A","B","B","B"] becomes counts of 3 for A and 3 for B. The next two lines build a max-heap. We negate each count, because heapq is a min-heap, then call heapify to build it in O(n).

The while heap loop runs one round at a time. Each round we set up an empty hold list and a counter run. The inner for _ in range(n + 1) runs at most n + 1 slots, because that is the spacing one task needs.

Inside, if the heap has tasks, we pop the largest count and negate it back. We run that task once, so its count drops by one. If the count is still positive, we hold it, negated again, to push back later. We add one to run for each task we actually ran.

After the round, we push every held count back onto the heap. Then we add to the time. If the heap is now empty, this was the last round, so we add only run, the real tasks run. We do not pad the end with idle slots. Otherwise the round was full, so we add n + 1, which counts both tasks and any idle slots in that round.

For the example, the first round runs A then B, both drop to 2, and we add 3 because the heap is not empty. The next round runs A then B again, both drop to 1, add 3. The last round runs A then B, the heap empties, so we add run which is 2. Total is 3 plus 3 plus 2, which is 8.

⏱️ Time and Space Complexity

The greedy heap approach counts tasks, then runs rounds. There are at most 26 task types, so the heap is tiny. The total work scales with the number of slots, which is O(n) in the count of tasks. The math formula approach skips the heap and just reads the counts, so it is O(n) time and O(1) extra space beyond the count array. Both are fast. The greedy choice of running the busiest task first is what makes it correct.

🧩 Key Takeaways

• ✅ The cooldown means the same task needs n slots between its runs.
• ✅ Running the busiest task first keeps the CPU full and cuts idle time.
• ✅ A max-heap of counts always gives you the task with the most copies left.
• ✅ Each round covers n + 1 slots, and you push leftover counts back after.
• ✅ The math formula gives the answer straight from the highest count and ties.

🚀 What’s Next?

• K Closest Points to Origin
• Find Median from Data Stream