Pattern this teaches:Greedy Scheduling and Sorting
Task Scheduler
A medium Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 2
- Core for
- 10 roles
The problem
Given a characters array representing tasks and a non-negative integer n representing a cooling interval, return the minimum number of intervals required to finish all tasks. Each task can be done in one interval. Between two identical tasks, there must be at least n intervals where a different task is performed or the CPU is idle.
Example 1
- Input
- tasks = ["A","A","A","A","B","B","C"], n = 2
- Output
- 10
- Why
- A needs a gap of two slots between runs: A _ _ A _ _ A _ _ A. B, B and C fill three of the six gap slots; the rest idle. Total 10.
Example 2
- Input
- tasks = ["A","A","A","B","B","B"], n = 0
- Output
- 6
- Why
- With no cooling constraint, tasks can be scheduled back-to-back: A B A B A B in 6 intervals.
Example 3
- Input
- tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
- Output
- 16
- Why
- The most frequent task A appears 6 times, requiring at least 5 gaps of 2 intervals each. The minimum is (6-1)*(2+1) + 1 = 16.
Constraints
- 1 <= tasks.length <= 10^4
- tasks[i] is an uppercase English letter
- 0 <= n <= 100
How to think about it
Updated 2026-09-29The most frequent task dictates the rigid structural frame of the timeline. If the highest frequency is m, it creates m - 1 mandatory cooling frames of width n + 1, plus trailing slots for tasks tied for top frequency. Everything else fills empty idle slots or expands the timeline naturally without adding extra idles.
Approaches, worst first
Priority queue simulation
time O(t log 26) · space O(1)
Store remaining task frequencies in a max-heap. In each round of n + 1 units, pull the most frequent distinct tasks, decrement their counts, and push survivors back for the next round while counting idle intervals.
Frequency bucket mathWrite this one
time O(t) · space O(1)
Find the maximum frequency maxCount and count how many distinct tasks share it. The baseline timeline length is (maxCount - 1) * (n + 1) + numMaxTasks. The true answer is the maximum of this formula and tasks.length.
Where people lose marks · 3
- Returning the formula result when the task variety outgrows the idle gaps. If there are enough distinct tasks to saturate all cooling slots, the answer is tasks.length, not the frame size.
- Failing to account for ties in highest frequency. If both A and B appear maxCount times, the final frame has width 2, not 1, which offsets the trailing term.
- Special casing n = 0 unnecessarily when the formula max(tasks.length, (maxCount - 1) * 1 + numMax) handles zero cooling automatically as long as the max with tasks.length is taken.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .