Task Scheduler solution and explanation
TCS
Google
9 more videos on this problem
Task Scheduler - Leetcode 621 - PythonNeetCode · 17:07 · 321K views
LeetCode 621. Task Scheduler (Algorithm Explained)Nick White · 10:29 · 74K views
Task Scheduler | Easy Intuition | Using Heap | Leetcode 621 | codestorywithMIKcodestorywithMIK · 28:26 · 63K views
Leetcode Problem , Task SchedulerAryan Mittal · 15:07 · 23K views
Task Scheduler - LeetCode 621 - Python [O(n) time and O(1) Space!]Deepti Talesra · 8:46 · 18K views
Task Scheduler | Using Greedy Only | No Heap | Leetcode 621 | codestorywithMIKcodestorywithMIK · 27:20 · 13K views
621. Task Scheduler | Leetcode | Medium | Java | Priority Queue | Striver's A to Z DSA Course/SheetAlgorithmHQ · 18:41 · 11K views
Task Scheduler | LeetCode 621 Heap ExplainedDestination FAANG · 21:07 · 2K views
Coding Interview Problem - Task SchedulerKnapsack · 5:49 · 1K views
Daily Leetcode #119: Jul 28, 2020 - 621. Task SchedulerProgramming Live with Larry · 9:22 · 591 views
The problem
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.
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.
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 of these tasks.
Constraints:
1 <= tasks.length <= 104tasks[i]is an uppercase English letter.0 <= n <= 100
Approach overview
Problem Overview: You are given a list of CPU tasks represented by characters and a cooldown interval n. The same task must be separated by at least n intervals. The goal is to compute the minimum number of time units required to finish all tasks, including idle slots if necessary.
Approach 1: Max Frequency Task-Based Greedy (O(n) time, O(1) space)
This approach relies on counting how often each task appears. The task with the highest frequency determines the schedule structure because its occurrences must be spaced by at least n intervals. Suppose the most frequent task appears maxFreq times. These tasks create maxFreq - 1 gaps that must each hold n other tasks or idle slots. The minimal frame size becomes (maxFreq - 1) * (n + 1). If multiple tasks share the same maximum frequency, their last occurrences extend the final frame. The final answer is max(totalTasks, (maxFreq - 1) * (n + 1) + countMax).
This works because the optimal schedule always spreads the most frequent tasks first and fills remaining gaps with other tasks. Counting frequencies with an array of size 26 keeps the space constant. The method heavily relies on greedy reasoning and efficient counting. In interviews, this formula-based reasoning shows strong pattern recognition and leads directly to the optimal solution.
Approach 2: Priority Queue (Heap) Simulation (O(n log k) time, O(k) space)
This approach simulates the scheduling process using a max heap. First, count task frequencies using a map or array. Push the frequencies into a max heap so the most frequent task is always processed first. At each cycle of length n + 1, repeatedly pop the most frequent tasks and execute them. After execution, decrease their remaining count and temporarily store them until the cycle ends.
When the cycle finishes, push any remaining tasks back into the heap. If the heap becomes empty early, idle intervals fill the remaining part of the cycle. Continue until all tasks are completed. This approach models the CPU scheduling process explicitly and uses a heap (priority queue) along with basic array counting.
The heap simulation is easier to reason about when deriving the greedy rule from scratch. It also generalizes well to variations where cooldown rules or task weights change.
Recommended for interviews: The greedy max-frequency formula is what most interviewers expect for this problem because it runs in O(n) time with constant space and demonstrates strong insight into scheduling constraints. The heap simulation is still valuable because it shows how to model the scheduling process step by step. Starting with the heap approach and then optimizing to the greedy formula is a strong interview progression.
Approach 1: Max Frequency Task-based approach
The key idea is to figure out the task with the maximum frequency and set its intervals accordingly.
Assume the task with the highest frequency appears max_count times. Arrange tasks such that the remaining tasks are fitted in between the most frequent task considering the cooldown period.
The formula for the minimum intervals required is determined by the max frequency task with necessary slots due to the cooling period. The result is the maximum of the total tasks or the formed slots, i.e., max(len(tasks), (max_count - 1) * (n + 1) + count_max), where count_max is the number of tasks with frequency equal to max_count.
from collections import Counter
def leastInterval(tasks, n):
task_counts = list(Counter(tasks).values())
max_count = max(task_counts)
count_max = task_counts.count(max_count)
return max(len(tasks), (max_count - 1) * (n + 1) + count_max)
# Example usage
print(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2)) # Output: 8import java.util.*;
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] map = new int[26];
for (char c : tasks) {
map[c - 'A']++;
}
Arrays.sort(map);
int max_val = map[25] - 1,
idle_slots = max_val * n;
for (int i = 24; i >= 0 && map[i] > 0; i--) {
idle_slots -= Math.min(map[i], max_val);
}
return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
}
public static void main(String[] args) {
Solution sol = new Solution();
char[] tasks = {'A','A','A','B','B','B'};
int n = 2;
System.out.println(sol.leastInterval(tasks, n)); // Output: 8
}
}#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int leastInterval(vector<char>& tasks, int n) {
vector<int> count(26, 0);
for (char task : tasks) {
count[task - 'A']++;
}
sort(count.begin(), count.end());
int max_count = count[25] - 1, idle_slots = max_count * n;
for (int i = 24; i >= 0 && count[i] > 0; i--) {
idle_slots -= min(count[i], max_count);
}
return idle_slots > 0 ? idle_slots + tasks.size() : tasks.size();
}
int main() {
vector<char> tasks = {'A','A','A','B','B','B'};
int n = 2;
return leastInterval(tasks, n); // Output: 8
}var leastInterval = function(tasks, n) {
let count = new Array(26).fill(0);
for (let task of tasks) {
count[task.charCodeAt() - 'A'.charCodeAt()]++;
}
count.sort((a, b) => a - b);
let maxVal = count[25] - 1;
let idleSlots = maxVal * n;
for (let i = 24; i >= 0 && count[i] > 0; i--) {
idleSlots -= Math.min(count[i], maxVal);
}
return idleSlots > 0 ? idleSlots + tasks.length : tasks.length;
};
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // Output: 8#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int leastInterval(char* tasks, int tasksSize, int n) {
int count[26] = {0};
for (int i = 0; i < tasksSize; i++) {
count[tasks[i] - 'A']++;
}
int maxCount = 0, numMax = 0;
for (int i = 0; i < 26; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
numMax = 1;
} else if (count[i] == maxCount) {
numMax++;
}
}
return fmax(tasksSize, (maxCount - 1) * (n + 1) + numMax);
}
int main() {
char tasks[] = {'A', 'A', 'A', 'B', 'B', 'B'};
int n = 2;
printf("%d\n", leastInterval(tasks, sizeof(tasks) / sizeof(tasks[0]), n));
return 0;
}using System;
using System.Linq;
class Solution {
public int LeastInterval(char[] tasks, int n) {
int[] map = new int[26];
foreach (char c in tasks) {
map[c - 'A']++;
}
Array.Sort(map);
int max_val = map[25] - 1;
int idle_slots = max_val * n;
for (int i = 24; i >= 0 && map[i] > 0; i--) {
idle_slots -= Math.Min(map[i], max_val);
}
return idle_slots > 0 ? idle_slots + tasks.Length : tasks.Length;
}
static void Main() {
char[] tasks = {'A','A','A','B','B','B'};
int n = 2;
Solution sol = new Solution();
Console.WriteLine(sol.LeastInterval(tasks, n)); // Output: 8
}
}This Python solution uses the collections module to count task frequencies. It calculates the minimum number of CPU intervals using the max frequency and the formula described. The result is the maximum between the total task count and the needed slots according to the maximum frequency task arrangement.
Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the maximum space used is the constant frequency counter.
Approach 2: Priority Queue (Heap)-based Simulation
Another way is to simulate the task processing using a priority queue to always pick the task with the highest remaining count that can be scheduled. A min-heap or a max-heap is useful to efficiently get the next task. As tasks are being processed, they are placed on cooldown before they can be executed again, managed by a cooldown queue.
from collections import Counter, deque
import heapq
def leastInterval(tasks, n):
task_counts = Counter(tasks)
max_heap = [-cnt for cnt in task_counts.values()]
heapq.heapify(max_heap)
time = 0
while max_heap:
temp = []
for _ in range(n + 1):
if max_heap:
temp.append(heapq.heappop(max_heap) + 1)
time += 1
if not max_heap and all(x == 0 for x in temp):
break
for count in temp:
if count < 0:
heapq.heappush(max_heap, count)
return time
# Example usage
print(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2)) # Output: 8import java.util.*;
class Solution {
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> map = new HashMap<>();
for (char task : tasks) map.put(task, map.getOrDefault(task, 0) + 1);
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.addAll(map.values());
int time = 0;
while (!pq.isEmpty()) {
List<Integer> temp = new ArrayList<>();
for (int i = 0; i <= n; ++i) {
if (!pq.isEmpty()) temp.add(pq.poll());
time++;
if (pq.isEmpty() && temp.isEmpty()) break;
}
for (int count : temp) if (--count > 0) pq.offer(count);
}
return time;
}
public static void main(String[] args) {
Solution sol = new Solution();
char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
int n = 2;
System.out.println(sol.leastInterval(tasks, n)); // Output: 8
}
}#include <queue>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> task_map;
for (char task : tasks) task_map[task]++;
priority_queue<int> pq;
for (auto& entry : task_map) pq.push(entry.second);
int time = 0;
while (!pq.empty()) {
vector<int> tmp;
for (int i = 0; i <= n; ++i) {
if (!pq.empty()) {
tmp.push_back(pq.top() - 1);
pq.pop();
}
time++;
if (pq.empty() && tmp.empty()) break;
}
for (int count : tmp) if (count > 0) pq.push(count);
}
return time;
}
int main() {
vector<char> tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
int n = 2;
return leastInterval(tasks, n); // Output: 8
}var leastInterval = function(tasks, n) {
const freq = new Map();
for (let task of tasks) {
freq.set(task, (freq.get(task) || 0) + 1);
}
const maxHeap = Array.from(freq.values()).sort((a, b) => b - a);
let time = 0;
while (maxHeap.length) {
const temp = [];
for (let i = 0; i <= n; i++) {
if (maxHeap.length) {
if (maxHeap[0] > 1) {
temp.push(maxHeap.shift() - 1);
} else {
maxHeap.shift();
}
}
time++;
if (!maxHeap.length && !temp.length) break;
}
maxHeap.push(...temp);
maxHeap.sort((a, b) => b - a);
}
return time;
};
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // Output: 8#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_TASKS 26
int cmp(const void* a, const void* b) {
return *(int*)b - *(int*)a;
}
int leastInterval(char* tasks, int tasksSize, int n) {
int taskCounts[MAX_TASKS] = {0};
for (int i = 0; i < tasksSize; i++) {
taskCounts[tasks[i] - 'A']++;
}
qsort(taskCounts, MAX_TASKS, sizeof(int), cmp);
int max_val = taskCounts[0];
int idle_slots = (max_val - 1) * n;
for (int i = 1; i < MAX_TASKS && taskCounts[i] > 0; i++) {
idle_slots -= taskCounts[i];
}
return idle_slots > 0 ? idle_slots + tasksSize : tasksSize;
}
int main() {
char tasks[] = {'A', 'A', 'A', 'B', 'B', 'B'};
int n = 2;
printf("%d\n", leastInterval(tasks, sizeof(tasks) / sizeof(tasks[0]), n));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
public int LeastInterval(char[] tasks, int n) {
Dictionary<char, int> dict = new Dictionary<char, int>();
foreach (char task in tasks) {
if (dict.ContainsKey(task))
dict[task]++;
else
dict[task] = 1;
}
PriorityQueue<int, int> pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
foreach (var kvp in dict) {
pq.Enqueue(kvp.Value, kvp.Value);
}
int time = 0;
while (pq.Count > 0) {
List<int> temp = new List<int>();
for (int i = 0; i <= n; ++i) {
if (pq.Count > 0) temp.Add(pq.Dequeue());
time++;
if (pq.Count == 0 && temp.Count == 0) break;
}
foreach (int count in temp) {
if (--count > 0) pq.Enqueue(count, count);
}
}
return time;
}
static void Main() {
char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
int n = 2;
Solution sol = new Solution();
Console.WriteLine(sol.LeastInterval(tasks, n)); // Output: 8
}
}This Python solution utilizes a priority queue (max-heap) to effectively handle the task scheduling with the intended cooldowns.
Time Complexity: O(N log M), where M is the distinct tasks. Space Complexity: O(M).
Approach 3: Default Approach
func leastInterval(tasks []byte, n int) int {
cnt := make([]int, 26)
x := 0
for _, c := range tasks {
c -= 'A'
cnt[c]++
x = max(x, cnt[c])
}
s := 0
for _, v := range cnt {
if v == x {
s++
}
}
return max(len(tasks), (x-1)*(n+1)+s)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Max Frequency Task-based approach | Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the maximum space used is the constant frequency counter. |
| Priority Queue (Heap)-based Simulation | Time Complexity: O(N log M), where M is the distinct tasks. Space Complexity: O(M). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max Frequency Greedy Formula | O(n) | O(1) | Best for interviews and optimal performance when tasks are limited to uppercase letters |
| Priority Queue (Heap) Simulation | O(n log k) | O(k) | Useful when reasoning step-by-step or when extending to generalized scheduling problems |
Frequently asked questions
Is Task Scheduler easy or hard?
Task Scheduler is classified as a medium difficulty problem on LeetCode with an acceptance rate around 60%. The main challenge is recognizing the greedy scheduling pattern and deriving the formula based on the most frequent tasks.
Task Scheduler Python/Java solution
Both Python and Java solutions typically implement either the greedy counting formula or a priority queue simulation. Python commonly uses collections.Counter and heapq, while Java uses an int array for counts or a PriorityQueue. The greedy solution is preferred due to its O(n) time and constant space.
How to solve Task Scheduler in O(n)?
Count the frequency of each task using a fixed array of size 26. Let maxFreq be the highest frequency and countMax be the number of tasks with that frequency. Compute the schedule length using (maxFreq - 1) * (n + 1) + countMax, then return the maximum of this value and the total task count.
What is the best approach for Task Scheduler?
The greedy max-frequency formula is the most efficient approach. Count the frequency of each task, identify the most frequent one, and compute the minimal frame using (maxFreq - 1) * (n + 1) + countMax. The final answer is the maximum between this value and the total number of tasks. This runs in O(n) time with O(1) space.
Is Task Scheduler asked at Google/Amazon/Meta?
Task Scheduler is a common medium-level scheduling and greedy problem frequently reported in interviews at Amazon, Google, and Meta. It tests frequency counting, greedy reasoning, and understanding of priority queues. Many companies use it to evaluate how candidates optimize from simulation to a mathematical greedy solution.
What data structure is used in Task Scheduler?
Two main structures are used depending on the approach. The greedy formula solution relies on an array for frequency counting. The simulation approach uses a max heap (priority queue) along with a queue or temporary list to manage cooldown cycles.
What is the time complexity of Task Scheduler?
The optimal greedy solution runs in O(n) time because it scans the task list once to compute frequencies. Space complexity is O(1) since there are at most 26 uppercase task types. A heap-based simulation approach runs in O(n log k) time where k is the number of distinct tasks.