Introduction

Task Scheduler is a classic Greedy scheduling problem.

You are given:

  • Tasks represented by capital letters
  • Cooling interval n

Goal:

Find the minimum time units required to complete all tasks.

Condition:

Same task must be separated by at least n intervals.

Example

Input

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

Output

8

Explanation

A → B → idleA → B → idle
A → B

Total = 8

Key Observation

The task with maximum frequency determines the structure of the schedule.

We arrange the most frequent task first and fill remaining slots.

Algorithm

  1. Count frequency of each task.
  2. Find maximum frequency.
  3. Count tasks having maximum frequency.
  4. Compute idle slots using formula.
  5. Return maximum of:
    • Total tasks
    • Required schedule length

Formula

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

Where:

maxFreq  = highest frequencymaxCount = number of tasks
having maxFreq frequency

Dry Run

Input

tasks = [A,A,A,B,B,B]n = 2

Frequencies

A = 3B = 3

Values

maxFreq = 3maxCount = 2

Formula

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

Answer

 8

Approach : Greedy

Arrange the most frequent task first.

The cooling period creates blocks between occurrences, and remaining tasks are used to fill these blocks.

Practice

Complexity Analysis

Time Complexity: O(n)Explanation: We count frequencies and scan the frequency array once.

Space Complexity: O(1)
Explanation: A fixed frequency array of size 26 is used for uppercase English letters.

Why This Problem is Important

Task Scheduler teaches greedy scheduling techniques and frequency-based optimization, which are common in system design and interview problems.

Common Beginner Mistakes

  • Simulating the entire schedule unnecessarily.
  • Ignoring tasks with equal maximum frequency.
  • Using incorrect formula.
  • Forgetting to compare with total task count.

Interview Tip

Always mention:

The most frequent task determines the minimum possible schedule length, and all other tasks are used to fill the cooling gaps.

Related Questions

  • Rearrange String k Distance Apart
  • Reorganize String
  • Gas Station
  • Jump Game
  • CPU Task Scheduling

Final Takeaway

Task Scheduler is a classic greedy scheduling problem. The key idea is that the task with the highest frequency creates the scheduling framework, and the final answer can be computed directly using a frequency-based formula without simulating the schedule.