# Task Scheduler > Run all tasks with a cooldown between two runs of the same task, in the fewest time slots. Why always running the task with the most copies left is optimal, simulated with a max-heap and a cooldown queue. - Track: DSA (Heaps & Priority Queues) - Level: Medium - Format: Step-through player - Author: Aayush Ostwal - Published: 25 October 2026 - Topics: Heap, Greedy, Queue - LeetCode: https://leetcode.com/problems/task-scheduler/ - Canonical URL: https://compoundengineer.com/library/dsa/task-scheduler Heap · Greedy with a cooldown queue Medium · O(N) time · O(1) space (at most 26 task types) ## Problem You are given an array tasks of capital letters, where each letter is a task type, and an integer n . Each time slot you can run one task or stay idle. Two runs of the same task must have at least n slots between them. Tasks may run in any order. Return the fewest slots needed to finish every task. Example 1 Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 (A B _ A B _ A B) Example 2 Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 (no cooldown: just run them all) Constraints 1 ≤ tasks.length ≤ 10^4 tasks[i] is an uppercase English letter 0 ≤ n ≤ 100 ## Brute force A computer processor runs one task per time slot. Tasks come in types, shown as letters. After it runs a task of some type, it must wait at least n slots before it may run the same type again. In the meantime it can run other types, or do nothing (stay idle). What is the fewest slots needed to finish all the tasks? - One task per slot, and each copy of a task runs exactly once. - Two runs of the same type must have at least n slots between them. - Idle slots count, so the answer is the number of tasks plus the idle slots we are forced to add. So the real question is how to avoid idle slots . An idle slot is forced when every task that is left is cooling down. That happens first to the task type with the most copies, because it has the most runs to space out. Here is the schedule for AAABBBC with n = 2 , written in rows of n + 1 = 3 slots, because that is how long a task needs before it can run again. The direct idea: try every order, keeping a table of how long each task type still has to wait, and take the shortest schedule. ### The problem with it The number of orders explodes. For 20 tasks it is already in the billions. We need a rule that picks the right task, instead of searching. ## How to think your way to the optimal solution Which task should run next? The type with the most copies left . That type is the one most likely to cause a forced idle slot later, so we should use up its copies as early as possible. If we leave it until the end, its runs cannot be spaced out, and idle slots are forced. Look at the figure: starting the busiest task late pushes the whole schedule back. So we need two things at every slot: - The ready task type with the most copies left. A heap, a box that hands you the biggest item first, gives us that. Python's heap gives the smallest, so we store counts as negative numbers. - A waiting area for tasks that have just run and are cooling down. It is a queue, a line where items leave in the order they came in. A task enters it with the time it will be ready, and goes back to the heap at that time. At each slot we run the best ready task if there is one. If the heap is empty and the cooling tasks are not ready yet, that slot is idle. ## The optimal solution ### Approach 1: a heap and a cooldown queue - Count how many copies each task type has, and put the counts in a heap, biggest first. - Each time slot: the heap has a task⟶run the busiest one, and if it has copies left, put it in the cooldown queue with the time it is ready - the heap is empty⟶the slot is idle - If the front of the cooldown queue is ready at this time, put it back in the heap. - Stop when the heap and the queue are both empty. The slot count is the answer. By hand , with the simpler AAABBB and n = 2 . (The player starts with AAABBBC : the extra C simply fills the first idle slot.) - Slot 1: run A (2 copies left). It will be ready at slot 4. - Slot 2: run B (2 left). It will be ready at slot 5. - Slot 3: the heap is empty and nothing is ready: idle. - Slot 4: A is ready again, so run it (1 left). Ready at slot 7. - Slot 5: B is ready, so run it (1 left). Ready at slot 8. - Slot 6: idle. - Slots 7 and 8: run the last A, then the last B. That is 8 slots: A B _ A B _ A B . Press Play to watch the heap and the cooldown queue. ### Approach 2: a formula The idea. The busiest task type sets the shape of the schedule. Say its count is m . Its runs need m − 1 gaps between them, and each gap, with the run itself, is a row of n + 1 slots. After the last gap there is a final row that holds only the last runs. If k task types tie for the most copies, they all appear in that final row. So the shape is (m − 1) × (n + 1) + k slots, and the other tasks fill the empty spots. If there are so many tasks that they do not all fit, no idle slot is needed, and the answer is simply the number of tasks. By hand , with AAABBBC and n = 2 : the busiest count is 3 (for A and B), so m = 3 , and k = 2 . The shape is (3 − 1) × 3 + 2 = 8. There are 7 tasks, so the answer is max(7, 8) = 8 . Cost. One pass to count the tasks, so O(N) time and O(1) space (at most 26 types). It gives the length but not the schedule. ## Complexity analysis | Approach | Time | Space | | --- | --- | --- | | Try every order | explodes | O(N) | | --- | --- | --- | | Heap and cooldown queue | O(N) | O(1) | | --- | --- | --- | | Formula | O(N) | O(1) | | --- | --- | --- | O(N) Time (heap). Here's why: N is the number of tasks. There are at most 26 task types, so the heap holds at most 26 items, and a heap step takes a small, fixed time. The schedule has at most N slots plus the idle ones, which is at most about N × (n + 1) in the worst case, so for a fixed n the total is a constant times N. O(1) Space. At most 26 types, so the heap and the queue each hold at most 26 items, however many tasks there are. ## Interviewer follow-ups These are the questions that usually come next. Open one to see an answer you could say out loud. "Return the actual schedule, not only the number of slots." What they are checking Whether you know which of your two solutions can do it. The formula only gives a length. A strong answer The formula cannot, but the heap version can. Each slot I write down which task I ran, or an idle mark if I ran none. At the end, that list is the schedule. The time stays the same, and the extra memory is the length of the schedule. "Explain why the formula works. Where do the idle slots come from?" What they are checking Whether you really understand the greedy idea, or have only memorised a formula. A strong answer The busiest type needs m − 1 gaps of n slots each between its runs, and that is a hard minimum. The other tasks can fill those gaps. If they fill all of them, there is no idle slot, and the answer is just the number of tasks. If they do not, the empty gaps are idle slots, and the length is the formula. So the answer is the larger of the two: the number of tasks, or the shape set by the busiest type. "Why a separate cooldown queue? Why not put the task straight back in the heap?" What they are checking Whether you understand what the cooldown queue is protecting. A strong answer If the task went straight back into the heap, it would be the busiest again, and the next slot would run it again, before its cooldown is over. That breaks the rule. The queue keeps the task out of the heap until its ready time, so the heap holds only tasks that are allowed to run now. ## Spot this pattern - You schedule items where the same kind of item cannot repeat too soon. - Handling the most frequent kind first avoids forced waiting later. - A heap picks the biggest available, and a queue holds the ones that are cooling down. ## Solution code ### Python ```python import heapq from collections import Counter, deque class Solution: def leastInterval(self, tasks, n): heap = [(-c, t) for t, c in Counter(tasks).items()] heapq.heapify(heap) # most copies left on top cooldown = deque() # (ready_time, -copies_left, task) time = 0 while heap or cooldown: time += 1 if heap: cnt, task = heapq.heappop(heap) # run the busiest ready task cnt += 1 # counts are negated: one run done if cnt: cooldown.append((time + n, cnt, task)) if cooldown and cooldown[0][0] == time: _, cnt, task = cooldown.popleft() # cooldown over: ready again heapq.heappush(heap, (cnt, task)) return time ``` ### Java ```java import java.util.*; class Solution { public int leastInterval(char[] tasks, int n) { int[] count = new int[26]; for (char t : tasks) count[t - 'A']++; PriorityQueue heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); for (int t = 0; t < 26; t++) if (count[t] > 0) heap.offer(new int[]{-count[t], t}); // most copies left on top Deque cooldown = new ArrayDeque<>(); // (ready_time, -copies_left, task) int time = 0; while (!heap.isEmpty() || !cooldown.isEmpty()) { time++; if (!heap.isEmpty()) { int[] top = heap.poll(); // run the busiest ready task int cnt = top[0] + 1; // counts are negated: one run done if (cnt != 0) cooldown.offer(new int[]{time + n, cnt, top[1]}); } if (!cooldown.isEmpty() && cooldown.peek()[0] == time) { int[] r = cooldown.poll(); // cooldown over: ready again heap.offer(new int[]{r[1], r[2]}); } } return time; } } ``` ### C++ ```cpp class Solution { public: int leastInterval(vector& tasks, int n) { unordered_map count; for (char t : tasks) count[t]++; priority_queue, vector>, greater<>> heap; for (auto& [t, c] : count) heap.push({-c, t}); // most copies left on top queue> cooldown; // (ready_time, -copies_left, task) int time = 0; while (!heap.empty() || !cooldown.empty()) { time++; if (!heap.empty()) { auto [cnt, task] = heap.top(); // run the busiest ready task heap.pop(); cnt++; // counts are negated: one run done if (cnt) cooldown.push({time + n, cnt, task}); } if (!cooldown.empty() && get<0>(cooldown.front()) == time) { auto [ready, cnt, task] = cooldown.front(); cooldown.pop(); // cooldown over: ready again heap.push({cnt, task}); } } return time; } }; ``` --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.