Task Scheduler

Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks can be done in any order. Each task takes one unit of time. For any unit of time, the CPU can either complete a task or be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array). There must be at least n units of time between any two same tasks.

Return the minimum number of units of time the CPU will need to complete all the given tasks.

Examples

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

Explanation:
A → B → idle → A → B → idle → A → B
Time units: 8

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6

Explanation: No cooldown needed
A → A → A → B → B → B

Example 3

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16

Explanation:
A → B → C → A → D → E → A → F → G → A → idle → idle → A → idle → idle → A

Intuition

Greedy Strategy: Always execute the most frequent task first (to spread it out).

Key Insight: The limiting factor is the most frequent task!

If task A appears f times with cooldown n:

• We need at least (f-1) * (n+1) + 1 time slots
• Between each A, we have n slots for other tasks

Approach:

1. Count task frequencies
2. Use max-heap to always pick most frequent available task
3. Track cooldown using queue

Pattern Recognition

This is a Heap + Queue Simulation problem:

• Max-heap for task priority (frequency)
• Queue for cooldown tracking
• Greedy task selection

Approach

Heap + Queue Simulation

1. Count frequencies using hash map
2. Max-heap with frequencies (most frequent first)
3. Simulate time:
   • Pop from heap (execute most frequent)
   • Decrease count, add to cooldown queue
   • After n time units, tasks become available again
4. Continue until both heap and queue empty

Time: O(n * tasks) in worst case, but typically much better

Math Formula (Optimal)

max_freq = frequency of most common task
max_count = number of tasks with max_freq

min_time = max(
  len(tasks),
  (max_freq - 1) * (n + 1) + max_count
)

This O(n) solution directly calculates answer!

Edge Cases

• n = 0 (no cooldown)
• Single task type
• All tasks unique
• Very large cooldown
• Many tasks with same max frequency

Complexity Analysis

Heap + Queue

• Time: O(n * k) where k = unique tasks

  • Simulation runs for total time
  • Each step: O(log k) heap operations

• Space: O(k)

  • Heap + queue + frequency map

Math Formula

• Time: O(n) to count frequencies
• Space: O(k) for frequency map