DSA Day 96/250: Task Scheduler (LeetCode 621)

[Click here to read for free.]

621. Task Scheduler

Difficulty: Medium Topics: Array, Hash Table, Greedy, Heap (Priority Queue), Counting Platform: LeetCode

Part of My 250 Days DSA Challenge

All problems from this challenge are saved in a single Medium list:

Data Structures and Algorithms: 250 Days Challenge | Curated by Rahul Kumar | Medium

[embed]List: Data Structures and Algorithms: 250 Days Challenge | Curated by Rahul Kumar | Medium Data Structures and Algorithms: 250 Days Challenge · A collection of DSA problems from my 250 Days Data Structure…medium.com

Problem Statement

You are given:

• An array of CPU tasks
• A cooling period n

After executing a task, the same task cannot be executed again for the next n intervals.

Each interval can be:

• Execute a task
• Stay idle

Your goal is to find:

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 → B → idle → A → B → idle → A → B

Practice System Design Interviews

If you want to practice real-world system design and technical interview questions, I’ve been exploring PracHub recently. It has company-specific interview questions, mock interview-style problems, and structured practice content for engineering interviews.

Practice here:

[embed]PracHub - Practice Tech Interview Questions (Updated 2026) Master your tech interviews with 8,000+ questions from top companies, validated by real candidates. Practice coding…prachub.com

Example 2

Input

tasks = ["A","C","A","B","D","B"]
n = 1

Output

6

Example 3

Input

tasks = ["A","A","A","B","B","B"]
n = 3

Output

10

Intuition (Important)

Most people initially think about simulating the scheduling process using:

• Queue
• Heap
• Cooling tracker

While that works, there is a much smarter observation.

The task with the highest frequency determines the overall schedule.

Why?

Because it creates the largest cooling gaps that must be filled.

Key Idea

Consider:

A A A

with:

n = 2

To satisfy cooling requirements:

A _ _ A _ _ A

There are:

2 gaps

between the three A’s.

Each gap must contain:

n = 2

slots.

Required structure becomes:

A _ _ A _ _ A

Total slots:

(3 - 1) × 2 = 4

These slots can be filled using other tasks.

If insufficient tasks exist, idle intervals are required.

Mathematical Formula

Let:

maxFreq = highest task frequency

and

maxCount = number of tasks having maxFreq

Then minimum intervals are:

(maxFreq - 1) × (n + 1) + maxCount

However, if enough tasks exist to fill all gaps, answer becomes:

tasks.length

Therefore:

answer =
Math.max(
    tasks.length,
    (maxFreq - 1) * (n + 1) + maxCount
)

This elegant formula eliminates the need for simulation.

Visual Understanding

Example

tasks =
[A,A,A,B,B,B]

n = 2

Frequencies:

A = 3
B = 3

Maximum frequency:

3

Number of tasks with maximum frequency:

2

Build the framework:

A _ _ A _ _ A

Number of partitions:

3 - 1 = 2

Each partition size:

n + 1 = 3

Formula:

(3 - 1) × (2 + 1) + 2

= 6 + 2
= 8

Answer:

8

Iteration Flow (Detailed Dry Run)

Input

tasks =
[A,A,A,B,B,B]

n = 2

Step 1: Count Frequencies

A = 3
B = 3

Maximum frequency:

maxFreq = 3

Tasks having max frequency:

maxCount = 2

Step 2: Apply Formula

(maxFreq - 1)
×
(n + 1)
+
maxCount

Substitute values:

(3 - 1)
×
(2 + 1)
+
2

2 × 3 + 2

8

Step 3: Compare With Total Tasks

Total tasks:

6

Answer:

max(6,8)

8

Final Answer

Approach

We first count the frequency of each task.

Then:

1. Find the highest frequency.
2. Count how many tasks have that highest frequency.
3. Build the scheduling formula.
4. Return the larger value between:

• Total tasks
• Formula result

This works because the most frequent tasks dictate the minimum schedule length.

Optimized JavaScript Solution

var leastInterval = function(tasks, n) {
    let freq = new Array(26).fill(0);
    for (let task of tasks) {
        freq[task.charCodeAt(0) - 65]++;
    }
    let maxFreq = Math.max(...freq);
    let maxCount = 0;
    for (let count of freq) {
        if (count === maxFreq) {
            maxCount++;
        }
    }
    let intervals =
        (maxFreq - 1) * (n + 1) + maxCount;
    return Math.max(tasks.length, intervals);
};

Code Dry Run (Step-by-Step Execution)

Input

tasks =
[A,A,A,B,B,B]

n = 2

Frequency Array

A = 3
B = 3

Maximum frequency:

3

Maximum frequency count:

2

Formula

(3 - 1) × (2 + 1) + 2

8

Compare

tasks.length = 6

max(6,8)

8

Final Output

8

Correct Answer

Complexity Analysis

Time Complexity

Counting frequencies:

O(n)

Finding maximum frequency:

O(26)

Overall:

O(n)

Space Complexity

Frequency array:

O(26)

O(1)

Why This Problem Is Important

This is one of the most famous Greedy interview problems.

It teaches:

✔ Pattern recognition ✔ Mathematical optimization ✔ Frequency counting ✔ Converting simulation problems into formulas

Many candidates try complicated heap solutions while the optimal solution is pure mathematics.

Key Takeaways

✔ Highest frequency task determines the schedule ✔ Cooling periods create partitions ✔ Fill partitions using remaining tasks ✔ Mathematical solutions can outperform simulations

Structured Learning Beyond Blogs

Courses

• DSA Course: ₹99
• System Design Course: ₹99
• DSA + System Design Combo: ₹149

Explore here:

[embed]Notes | Linktree linktr.ee

Day 96/250 Completed

Today we learned:

✔ Frequency-based greedy thinking ✔ Scheduling optimization ✔ Mathematical problem solving ✔ Avoiding unnecessary simulation

This is one of the most frequently asked Greedy + Frequency Counting interview questions.