Skip to content

Volume ITechnology

4.17.5 — Task Scheduler ​

LeetCode 621 · Medium

The problem ​

Each task takes one unit of time. The same task cannot run again until n units have passed. Different tasks have no restriction. The CPU may idle. Return the minimum total time to run everything.

tasks = ["A","A","A","B","B","B"], n = 2   →  8
    A B idle A B idle A B

tasks = ["A","A","A","B","B","B"], n = 0   →  6

What the problem is really asking ​

Idle time only happens when every task that is still waiting to run is cooling down. So the real question is: in what order should the tasks run, so that the CPU is idle as little as possible?

The brute force, and where it wastes work ​

Try every possible order of the tasks and keep the shortest valid schedule. With 10,000 tasks that is far beyond any computer. Even a careful search that tries each allowed task at each step branches at every step.

The waste in one sentence: it tries orders that are obviously worse, when a simple rule, "run the most common task that is allowed right now", is always at least as good.

The pattern ​

The greedy rule is: at every step, run the most frequent task that is currently allowed.

Why the most frequent? Because it is the one most likely to cause idling later. Spending its copies early spreads them out; leaving them until the end forces gaps you cannot fill.

That needs "the currently largest count", repeatedly, from a changing collection — which is a max-heap. Plus a queue holding tasks that are cooling down and cannot yet be chosen.

Solution 1 — simulation with a heap ​

python
import heapq
from collections import Counter, deque

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)  # (1)
        heap = [-c for c in counts.values()]        # (2) max-heap by negation
        heapq.heapify(heap)

        cooling = deque()          # (3) (remaining count, time it becomes available)
        time = 0  # (4)

        while heap or cooling:  # (5)
            time += 1  # (6)

            if heap:  # (7)
                remaining = heapq.heappop(heap) + 1     # (8) one copy used (negated)
                if remaining:                            # (9) still copies left
                    cooling.append((remaining, time + n))
            # else: the CPU idles this tick

            if cooling and cooling[0][1] == time:  # (10)
                heapq.heappush(heap, cooling.popleft()[0])

        return time  # (11)
ts
function leastInterval(tasks: string[], n: number): number {
  const counts = new Map<string, number>();  // (1)
  for (const t of tasks) counts.set(t, (counts.get(t) ?? 0) + 1);

  const heap = new MaxHeap<number>();  // (2)
  for (const c of counts.values()) heap.push(c);

  const cooling: Array<[number, number]> = [];  // (3)
  let time = 0;  // (4)

  while (heap.size || cooling.length) {  // (5)
    time++;  // (6)
    if (heap.size) {  // (7)
      const remaining = heap.pop()! - 1;  // (8)
      if (remaining > 0) cooling.push([remaining, time + n]);  // (9)
    }
    if (cooling.length && cooling[0][1] === time) {  // (10)
      heap.push(cooling.shift()![0]);
    }
  }

  return time;  // (11)
}

Line by line ​

(1) Count how many copies of each task there are. The task names do not matter, only the counts.

(2) A heap of counts, biggest first. Python's heap keeps the smallest at the front, so we store negative counts. The most copies becomes the most negative number, which sits at the front. In TypeScript, MaxHeap is the heap from 4.16 with the comparison flipped.

(3) A queue of tasks that are cooling down. Each entry is "how many copies are left" and "the time at which this task may run again".

(4) The clock starts at 0.

(5) Keep going while any task still has copies left, either ready in the heap or waiting in the queue.

(6) One unit of time passes. This happens every turn, whether or not a task runs, which is how idle time gets counted.

(7) If any task is ready, run one.

(8) Take the task with the most copies left, and use one copy. The stored count is negative, so adding 1 moves it one step toward zero, which means one fewer copy.

(9) If copies are left, the task starts cooling. It may run again at time + n. If no copies are left, the task is finished and simply disappears.

(10) A task whose cooldown ends now becomes ready again. Tasks enter the queue in time order, so only the front of the queue can be ready. No second heap is needed.

(11) The clock now shows the total time, including idle units.

, so heappop gives the largest and + 1 decrements it (adding 1 to a negative number moves it towards zero).

The queue is naturally ordered by availability time, because tasks enter it in increasing time order. So only the front ever needs checking — no second heap is required.

When the heap is empty but the queue is not, the CPU idles. The time += 1 happens unconditionally at the top, which is what counts the idle tick.

O(\text{total tasks} \times \log 26), effectively O(\text{total tasks}).

Let's derive this:

  • Time Complexity: Constructing the initial frequencies takes O(N) where N is the number of tasks. The heap contains at most 26 elements (the English alphabet). Each heappop and heappush takes O(\log 26) time, which is practically O(1). Since each task is pushed and popped a number of times proportional to its count, the loop runs O(N) times. Thus, the total time is O(N).
  • Space Complexity: The counts map, heap, and cooling queue all store at most 26 elements. So the space complexity is strictly O(1) (or O(26)).

Solution 2 — the formula, O(n) with no heap ​

There is a closed formula, and understanding it teaches more than the simulation.

Let maxCount be the highest frequency, and let numMax be how many different tasks share that frequency.

Build a skeleton out of the most frequent task. With maxCount = 3 and n = 2, task A forces this shape:

A _ _ A _ _ A

There are maxCount − 1 gaps, each of width n, plus the final A. So the skeleton takes:

(\text{maxCount} - 1) \times (n + 1) + 1

Now if several tasks tie for the highest frequency, each of them needs a slot in the final block too:

(\text{maxCount} - 1) \times (n + 1) + \text{numMax}

And then the catch. If there are plenty of other tasks, they fill every gap and the answer is simply len(tasks) — no idling at all. The formula can even come out smaller than the number of tasks in that case, which would be nonsense.

So take the larger of the two:

python
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)  # (12)
        max_count = max(counts.values())  # (13)
        num_max = sum(1 for c in counts.values() if c == max_count)  # (14)

        return max(len(tasks), (max_count - 1) * (n + 1) + num_max)  # (15)

O(\text{total tasks}) time, O(1) space.

Line by line. (12) Count each task. (13) The highest count, maxCount. (14) How many different tasks share that highest count, numMax. (15) The skeleton length from the formula, or the number of tasks if that is larger, because the CPU can never finish faster than one task per unit of time.

Checking it on the examples ​

["A","A","A","B","B","B"], n = 2. max_count = 3, num_max = 2 (both A and B).

Formula: (3−1) × (2+1) + 2 = 6 + 2 = 8. Task count is 6. Take the max → 8 ✓.

With n = 0: (3−1) × 1 + 2 = 4. Task count is 6. Take the max → 6 ✓. Here the len(tasks) term is what saves it, because with no cooldown there is never any idling.

Trace for the simulation ​

Let's trace ["A", "A", "B", "B"], n = 1 using the heap simulation.

  • counts = {'A': 2, 'B': 2}. heap = [-2(A), -2(B)].
  • time = 1: pop A (-2). Remaining is 1. Add to cooling: (1, time + n) -> (1, 1+1=2). Heap: [-2(B)].
  • time = 2: pop B (-2). Remaining is 1. Add to cooling: (1, 2+1=3). Cooling [ (1(A), 2) ] has maturity 2 == time, so push A back to heap: [-1(A)].
  • time = 3: pop A (-1). Remaining 0. Cooling [ (1(B), 3) ] has maturity 3 == time, push B back: [-1(B)].
  • time = 4: pop B (-1). Remaining 0. Heap and cooling are empty.
  • Total time is 4. Sequence: A, B, A, B.

Edge cases ​

  • n = 0. No cooldown, so no idling. The answer is the number of tasks.
  • Only one kind of task, like ["A", "A", "A"] with n = 2. Every gap must be idle: A _ _ A _ _ A, so 7.
  • Many different tasks. The gaps fill up, and the answer is again just the number of tasks.

Which to write ​

The formula is shorter and faster. The simulation is easier to trust and it generalises — if the problem later asks which task runs at each moment, or gives tasks different durations, the formula collapses and the heap still works.

Say the greedy rule, describe the simulation, then offer the formula with its derivation. That order shows you understand why the formula is true rather than having memorised it.

Where this goes next ​

  • Reorganize String — rearrange a string so no two neighbours match. Same greedy rule with n = 1, and it is impossible exactly when maxCount > (len+1)/2, which is this formula in disguise.
  • Rearrange String k Distance Apart — the same with a general gap.
  • Real scheduling — rate limiting, retry backoff, and job schedulers all face "run the most urgent thing that is currently allowed". Chapter 11.18 builds a job scheduler properly.

What the interviewer will push on ​

"Why run the most frequent task first?" It is the one that will cause idling later, so its copies must be spread out early.

"Derive the formula." Skeleton of maxCount − 1 gaps of width n, plus the last block containing every task tied at the maximum.

"Why the max with len(tasks)?" When there are enough other tasks to fill every gap, there is no idling and the answer is just the task count.

"What if tasks had different durations?" The formula breaks; the heap simulation still works. This is the question that rewards having both.

One thing to volunteer: draw the skeleton A _ _ A _ _ A before writing the formula. Every term becomes visible from the picture, and it is far more convincing than the algebra alone.

Next: 4.17.6 Design Twitter — a heap doing a k-way merge inside a design problem.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet