Skip to main content
Talentd

Task Scheduler - Solution & Explanation

MediumArrayHash TableGreedySorting17 min readAsked at: Amazon, Microsoft, Apple +21
Practice this problem

Problem Statement

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 <= 104
  • tasks[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.

This C solution computes the frequency of each task using an array of size 26. It calculates the maximum frequency and the number of tasks with this frequency. The least number of intervals is calculated using the formula discussed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the space for the frequency array is constant.

Try this approach in the editor →

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.

This C solution uses sorting as an auxiliary step to simulate the behavior of a priority queue. The task processing works by repeatedly selecting the most frequent task, calculating available idle slots, and filling them as necessary.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N log N), where N is determined by sorting. Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoC#

Python

Java

C++

Go

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Max Frequency Task-based approach

Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the space for the frequency array is constant.

Priority Queue (Heap)-based Simulation

Time Complexity: O(N log N), where N is determined by sorting. Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Max Frequency Greedy FormulaO(n)O(1)Best for interviews and optimal performance when tasks are limited to uppercase letters
Priority Queue (Heap) SimulationO(n log k)O(k)Useful when reasoning step-by-step or when extending to generalized scheduling problems

Video Solution

Task Scheduler - Leetcode 621 - Python • NeetCode • 321,235 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Task Scheduler with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Minimum Time to Finish All Jobs II

Next

Generate Schedule