280. Task Scheduler
🔗 LeetCode Problem: 621. Task Scheduler
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting
Problem Statement
Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just 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), that is, there must be at least n units of time between any two same tasks.
Return the least number of units of times that the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.
Example 2:
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.
Example 3:
Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A
Constraints:
- 1 <= tasks.length <= 10^4
- tasks[i] is upper-case English letter
- 0 <= n <= 100
🌟 Understanding the Problem
What is the cooldown constraint?
Task: A
Cooldown: n = 2
First A at time 0:
[A, _, _, ...]
↑
time 0
Can execute A again at time 3 (after 2 units):
[A, X, X, A, ...]
↑ ↑
time 0 time 3
Between positions 0 and 3: 2 units of time (positions 1, 2)
Cannot execute at time 1 or 2:
[A, A, ...] ✗ (only 0 units between)
[A, X, A, ...] ✗ (only 1 unit between)
Simple Example:
tasks = ["A", "A", "A", "B", "B", "B"], n = 2
Frequency count:
A: 3 times
B: 3 times
One valid schedule:
Time: 0 1 2 3 4 5 6 7
Task: [A][B][?][A][B][?][A][B]
↑ ↑ ↑ ↑
A's with 2 units between each
Positions 2 and 5 can be filled with anything
or left idle
Total time: 8 units
Key Observations:
1. Same task needs n cooldown between executions
→ Can't do A, then immediately A if n > 0
2. Different tasks have NO cooldown
→ A then B is always allowed
3. We can be idle (do nothing)
→ If no task available, must wait
4. Want MINIMUM time
→ Schedule tasks efficiently
→ Minimize idle time
🌟 The Natural Thinking Process
When you first see this problem:
Question: Schedule tasks with cooldown, minimize time
First Thought: "Simulate the scheduling process"
- Keep track of when each task can be executed
- Use heap to always pick available task
- If no task available, be idle
Is this optimal? Works but complex!
Let's try it to understand the problem better.
The Evolution:
BRUTE FORCE THINKING:
"Simulate time unit by unit"
"Track cooldown for each task"
"Use max-heap to pick most frequent available task"
Time: O(total_time × log k) where k = unique tasks
⬇
REALIZATION 1:
"Simulation works but is there a pattern?"
"Most frequent task determines structure!"
⬇
OPTIMIZATION 1: Greedy with Heap
"Always execute most frequent available task"
"Fill gaps with other tasks or idle"
Still O(total_time × log k)
⬇
REALIZATION 2:
"Can I calculate answer directly?"
"Most frequent task creates 'slots'"
"Other tasks fill these slots!"
⬇
OPTIMIZATION 2: Math Formula
"Calculate based on most frequent task"
"No simulation needed!"
Time: O(n) - just count frequencies! ✨
🎯 Approach 1: Simulation with Max-Heap ⭐
The First Natural Solution
The Thought Process:
Step 1: Understand constraints
"Same task needs n cooldown"
"Different tasks can be consecutive"
Step 2: How to schedule?
"At each time unit, pick a task"
"Which task? Most frequent available!"
"Why most frequent? Finish them early to reduce idle"
Step 3: Track cooldown
"After executing task, can't use for n units"
"Use a queue to track when tasks become available"
Let's simulate step by step!
Visual Tracking - Complete Example
Input: tasks = ["A","A","A","B","B","B"], n = 2
Frequency count:
A: 3
B: 3
═══════════════════════════════════════════════════════════════
SIMULATION - Time Unit by Time Unit
═══════════════════════════════════════════════════════════════
Max-Heap (by frequency): [A:3, B:3]
Cooldown Queue: []
Schedule: []
─────────────────────────────────────────────────────────────
Time = 0
─────────────────────────────────────────────────────────────
Available tasks: [A:3, B:3]
Pick most frequent: A (freq=3)
Execute A:
- Decrease frequency: A now has 2 remaining
- A on cooldown until time 3 (current=0, cooldown=2)
Schedule: [A]
Heap: [B:3]
Cooldown Queue: [(A:2, available_at=3)]
─────────────────────────────────────────────────────────────
Time = 1
─────────────────────────────────────────────────────────────
Check cooldown queue: A available at 3, not yet
Available tasks: [B:3]
Pick: B (freq=3)
Execute B:
- Decrease frequency: B now has 2 remaining
- B on cooldown until time 4
Schedule: [A, B]
Heap: []
Cooldown Queue: [(A:2, 3), (B:2, 4)]
─────────────────────────────────────────────────────────────
Time = 2
─────────────────────────────────────────────────────────────
Check cooldown queue: Nothing available yet
Available tasks: []
Must be IDLE
Schedule: [A, B, idle]
Heap: []
Cooldown Queue: [(A:2, 3), (B:2, 4)]
─────────────────────────────────────────────────────────────
Time = 3
─────────────────────────────────────────────────────────────
Check cooldown queue: A available at 3! Add back to heap
Available tasks: [A:2]
Pick: A (freq=2)
Execute A:
- Decrease: A now has 1 remaining
- On cooldown until time 6
Schedule: [A, B, idle, A]
Heap: []
Cooldown Queue: [(B:2, 4), (A:1, 6)]
─────────────────────────────────────────────────────────────
Time = 4
─────────────────────────────────────────────────────────────
Check cooldown queue: B available at 4! Add to heap
Available tasks: [B:2]
Pick: B (freq=2)
Execute B:
- Decrease: B now has 1 remaining
- On cooldown until time 7
Schedule: [A, B, idle, A, B]
Heap: []
Cooldown Queue: [(A:1, 6), (B:1, 7)]
─────────────────────────────────────────────────────────────
Time = 5
─────────────────────────────────────────────────────────────
Check cooldown queue: Nothing available yet
Available tasks: []
Must be IDLE
Schedule: [A, B, idle, A, B, idle]
Heap: []
Cooldown Queue: [(A:1, 6), (B:1, 7)]
─────────────────────────────────────────────────────────────
Time = 6
─────────────────────────────────────────────────────────────
Check cooldown queue: A available at 6! Add to heap
Available tasks: [A:1]
Pick: A (freq=1)
Execute A:
- Decrease: A now has 0 remaining
- Done with A!
Schedule: [A, B, idle, A, B, idle, A]
Heap: []
Cooldown Queue: [(B:1, 7)]
─────────────────────────────────────────────────────────────
Time = 7
─────────────────────────────────────────────────────────────
Check cooldown queue: B available at 7! Add to heap
Available tasks: [B:1]
Pick: B (freq=1)
Execute B:
- Decrease: B now has 0 remaining
- Done with B!
Schedule: [A, B, idle, A, B, idle, A, B]
Heap: []
Cooldown Queue: []
All tasks done!
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Final schedule: A -> B -> idle -> A -> B -> idle -> A -> B
Total time: 8 units ✓
Breakdown:
- Executed 6 tasks (3 A's, 3 B's)
- Had 2 idle periods
- Total: 6 + 2 = 8
Implementation
import java.util.*;
/**
* Simulation with Max-Heap
* Time: O(total_time × log k) where k = unique tasks
* Space: O(k)
*/
class Solution {
public int leastInterval(char[] tasks, int n) {
// Count frequencies
Map<Character, Integer> freqMap = new HashMap<>();
for (char task : tasks) {
freqMap.put(task, freqMap.getOrDefault(task, 0) + 1);
}
// Max-heap by frequency
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.addAll(freqMap.values());
// Queue for cooldown: (frequency, available_time)
Queue<int[]> cooldownQueue = new LinkedList<>();
int time = 0;
while (!maxHeap.isEmpty() || !cooldownQueue.isEmpty()) {
time++;
// Check if any task is off cooldown
if (!cooldownQueue.isEmpty() && cooldownQueue.peek()[1] == time) {
maxHeap.offer(cooldownQueue.poll()[0]);
}
// Execute most frequent available task
if (!maxHeap.isEmpty()) {
int freq = maxHeap.poll();
freq--;
if (freq > 0) {
// Put on cooldown
cooldownQueue.offer(new int[]{freq, time + n});
}
}
// else: idle (time still increments)
}
return time;
}
}
⏰ Time: O(total_time × log k) - Simulate each time unit
💾 Space: O(k) - Heap and queue
Why This Works but is Inefficient:
✓ Correctly simulates the scheduling
✓ Always picks most frequent available
✓ Handles cooldown properly
✗ Simulates every time unit
✗ Can be slow when total_time is large
✗ Is there a pattern we can exploit?
💡 The First AHA Moment - Understanding the Structure
OBSERVATION from simulation:
tasks = ["A","A","A","B","B","B"], n = 2
Result: A -> B -> idle -> A -> B -> idle -> A -> B
Pattern:
A creates the "structure"
A appears 3 times with 2 gaps between
Structure from A:
A _ _ A _ _ A
B fills the gaps:
A B _ A B _ A B
Still have empty slots → idle:
A B idle A B idle A B
KEY INSIGHT:
The MOST FREQUENT task determines the structure!
Other tasks fill the gaps!
If most frequent task appears maxFreq times,
we need (maxFreq - 1) "chunks" of (n + 1) slots each,
plus 1 final execution!
💡 The Second AHA Moment - The Math Formula
MATHEMATICAL OBSERVATION:
Most frequent task: A with count = 3
Cooldown: n = 2
Structure created by A:
[A][?][?][A][?][?][A]
└─chunk─┘└─chunk─┘ final
Chunks: (maxFreq - 1) = (3 - 1) = 2
Chunk size: (n + 1) = (2 + 1) = 3
Final: 1 (last A)
Total slots: 2 × 3 + 1 = 7
But we have 6 tasks total (3 A's, 3 B's)!
Need at least 6 slots.
Formula:
time = max(
(maxFreq - 1) × (n + 1) + count_of_max_freq_tasks,
total_tasks
)
= max((3-1)×(2+1) + 2, 6) // B also has max freq!
= max(6 + 2, 6)
= max(8, 6)
= 8 ✓
WHY MAX?
If tasks are many and varied:
Can fill all gaps → no idle
Time = total_tasks
If most frequent task dominates:
Creates idle slots
Time = formula
Take maximum of both!
🎯 Approach 2: Math Formula (Optimal) ⭐⭐⭐
The Optimal Solution
The Evolution of Thought:
Simulation: Works but slow
⬇
Observation: Most frequent task creates structure
⬇
Pattern: (maxFreq - 1) chunks of (n + 1) slots + final
⬇
Formula: Direct calculation without simulation! ✨
Understanding the Math Formula - Complete Explanation
Why does this formula work?
THE CORE PRINCIPLE:
Most frequent task(s) determine minimum time structure.
Step 1: Find max frequency
Count all task frequencies
maxFreq = highest frequency
Step 2: Count tasks with max frequency
countMax = number of tasks with maxFreq
Step 3: Calculate minimum time from structure
Chunks: (maxFreq - 1)
Chunk size: (n + 1)
Final row: countMax (all max freq tasks)
Formula time = (maxFreq - 1) × (n + 1) + countMax
Step 4: Compare with total tasks
If total tasks > formula time:
No idle needed! Tasks fill everything!
Time = total tasks
Otherwise:
Need idle slots
Time = formula time
Final: time = max(formula_time, total_tasks)
WHY This Formula is Correct - Critical Reasoning
The Core Question:
Why does (maxFreq - 1) × (n + 1) + countMax work?
What does each part represent?
Answer Through Detailed Reasoning:
PART 1: Understanding (maxFreq - 1)
═══════════════════════════════════════════════════════════════
If task A appears maxFreq times:
A _ _ _ A _ _ _ A _ _ _ A ... A
Between first and last A:
(maxFreq - 1) intervals
Example: maxFreq = 4
A _ _ _ A _ _ _ A _ _ _ A
└──1──┘└──2──┘└──3──┘
3 intervals = (4 - 1) = (maxFreq - 1) ✓
═══════════════════════════════════════════════════════════════
PART 2: Understanding (n + 1)
═══════════════════════════════════════════════════════════════
Each interval must have:
- 1 A at the start
- n positions for cooldown
Total: 1 + n = (n + 1) positions
Example: n = 2
[A][?][?] = 1 + 2 = 3 positions
↑ └─n─┘
1
This is ONE "chunk" ✓
═══════════════════════════════════════════════════════════════
PART 3: Understanding + countMax
═══════════════════════════════════════════════════════════════
After all chunks, we have the final execution(s).
If only A has maxFreq:
Structure: chunk chunk chunk ... A (final)
Final: +1
If A and B both have maxFreq:
Structure: chunk chunk chunk ... [A B] (final)
Final: +2
If A, B, C have maxFreq:
Final: +3
countMax = number of tasks with maxFreq
Final row size = countMax ✓
═══════════════════════════════════════════════════════════════
PUTTING IT TOGETHER:
═══════════════════════════════════════════════════════════════
Total positions needed:
(maxFreq - 1) × (n + 1) + countMax
└───chunks───┘ └─chunk─┘ └─final─┘
size
Example 1: A:3, B:3, n=2
maxFreq = 3
countMax = 2 (both A and B)
Formula: (3-1) × (2+1) + 2
= 2 × 3 + 2
= 6 + 2
= 8
Structure:
Chunk 1: [A][B][?]
Chunk 2: [A][B][?]
Final: [A][B]
Total: 3 + 3 + 2 = 8 ✓
Example 2: A:5, B:3, C:3, n=2
maxFreq = 5
countMax = 1 (only A)
Formula: (5-1) × (2+1) + 1
= 4 × 3 + 1
= 12 + 1
= 13
Structure:
Chunk 1: [A][B][C]
Chunk 2: [A][B][C]
Chunk 3: [A][?][?]
Chunk 4: [A][?][?]
Final: [A]
B and C fill first 2 chunks perfectly!
Chunks 3 and 4 need idle.
WHY max(formula, total_tasks) - Critical Reasoning
The Core Question:
Why do we need max(formula_time, total_tasks)?
When is formula_time not enough?
Answer Through Examples:
CASE 1: Formula time > Total tasks
═══════════════════════════════════════════════════════════════
Example: tasks = ["A","A","A","B","B"], n = 2
Count:
A: 3 (maxFreq)
B: 2
Total tasks: 5
Formula:
(3-1) × (2+1) + 1 = 2×3 + 1 = 7
Compare:
Formula: 7
Total: 5
max(7, 5) = 7 ✓
Why 7?
Structure: [A][B][?][A][B][?][A]
└─chunk─┘└─chunk─┘ final
Only 5 tasks, but need 7 slots due to cooldown!
Must have idle! ✓
═══════════════════════════════════════════════════════════════
CASE 2: Total tasks > Formula time (CRITICAL CASE!)
═══════════════════════════════════════════════════════════════
Example: tasks = ["A","A","A","B","B","B","C","C","C"], n = 2
Count:
A: 3
B: 3
C: 3
All have maxFreq = 3
Total tasks: 9
Formula:
(3-1) × (2+1) + 3 = 2×3 + 3 = 9
But what if we had:
tasks = ["A","A","A","B","B","B","C","C","C","D","D"], n = 2
A,B,C: 3 each (maxFreq)
D: 2
Total: 11
Formula:
(3-1) × (2+1) + 3 = 9
Compare:
Formula: 9
Total: 11
max(9, 11) = 11 ✓
Why 11?
Structure has only 9 slots from formula:
Chunk 1: [A][B][C]
Chunk 2: [A][B][C]
Final: [A][B][C]
But we have 11 tasks! Where do D's go?
Answer: Fill the chunks MORE densely!
Chunk 1: [A][B][C]
Chunk 2: [A][B][C]
Final: [A][B][C][D][D]
└──────5────────┘
Final row can have MORE than just max freq tasks!
As long as cooldown is satisfied, we can add more!
Total time: 3 + 3 + 5 = 11 ✓
No idle needed! Tasks fill all slots! ✓
═══════════════════════════════════════════════════════════════
THE GENERAL RULE:
═══════════════════════════════════════════════════════════════
Formula time = minimum time needed due to COOLDOWN constraint
Total tasks = minimum time needed to execute ALL tasks
Take MAX because:
- Can't be less than formula (cooldown constraint)
- Can't be less than total (must execute all tasks)
Whichever is larger is the answer! ✓
INTUITION:
If most frequent task dominates:
→ Formula time larger → need idle
If many varied tasks:
→ Total tasks larger → no idle, fill densely
MAX handles both cases! ✨
Visual Tracking - Complete Examples
EXAMPLE 1: tasks = ["A","A","A","B","B","B"], n = 2
═══════════════════════════════════════════════════════════════
Step 1: Count frequencies
A: 3
B: 3
Step 2: Find max frequency and count
maxFreq = 3
countMax = 2 (both A and B have freq 3)
Step 3: Calculate formula time
(maxFreq - 1) × (n + 1) + countMax
= (3 - 1) × (2 + 1) + 2
= 2 × 3 + 2
= 6 + 2
= 8
Step 4: Calculate total tasks
total = 6
Step 5: Take maximum
time = max(8, 6) = 8 ✓
Visualization:
Chunk 1: [A][B][idle]
Chunk 2: [A][B][idle]
Final: [A][B]
Total: 3 + 3 + 2 = 8 ✓
═══════════════════════════════════════════════════════════════
EXAMPLE 2: tasks = ["A","A","A","B","B","B"], n = 0
═══════════════════════════════════════════════════════════════
Step 1: Count frequencies
A: 3, B: 3
Step 2: Max frequency
maxFreq = 3
countMax = 2
Step 3: Formula time
(3 - 1) × (0 + 1) + 2
= 2 × 1 + 2
= 2 + 2
= 4
Step 4: Total tasks
total = 6
Step 5: Maximum
time = max(4, 6) = 6 ✓
Visualization:
No cooldown (n=0)!
Can do: [A][B][A][B][A][B]
No idle needed!
Formula gives 4, but need 6 for all tasks.
Max picks 6 ✓
═══════════════════════════════════════════════════════════════
EXAMPLE 3: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
═══════════════════════════════════════════════════════════════
Step 1: Count frequencies
A: 6
B,C,D,E,F,G: 1 each
Step 2: Max frequency
maxFreq = 6
countMax = 1
Step 3: Formula time
(6 - 1) × (2 + 1) + 1
= 5 × 3 + 1
= 15 + 1
= 16
Step 4: Total tasks
total = 12
Step 5: Maximum
time = max(16, 12) = 16 ✓
Visualization:
Chunk 1: [A][B][C]
Chunk 2: [A][D][E]
Chunk 3: [A][F][G]
Chunk 4: [A][idle][idle]
Chunk 5: [A][idle][idle]
Final: [A]
6 other tasks fill first 3 chunks
Chunks 4 and 5 need idle
Total: 3+3+3+3+3+1 = 16 ✓
Implementation
import java.util.*;
/**
* Math Formula (Optimal)
* Time: O(n) where n = tasks.length
* Space: O(1) - only 26 possible tasks
*/
class Solution {
public int leastInterval(char[] tasks, int n) {
// Count frequencies
int[] freq = new int[26];
for (char task : tasks) {
freq[task - 'A']++;
}
// Find max frequency
int maxFreq = 0;
for (int f : freq) {
maxFreq = Math.max(maxFreq, f);
}
// Count how many tasks have max frequency
int countMax = 0;
for (int f : freq) {
if (f == maxFreq) {
countMax++;
}
}
// Calculate time using formula
int formulaTime = (maxFreq - 1) * (n + 1) + countMax;
// Return max of formula time and total tasks
return Math.max(formulaTime, tasks.length);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 0)); // 6
System.out.println(sol.leastInterval(
new char[]{'A','A','A','A','A','A','B','C','D','E','F','G'}, 2)); // 16
}
}
⏰ Time: O(n) - Count frequencies once
💾 Space: O(1) - Fixed array of size 26
Why This is Optimal:
✓ O(n) time - single pass
✓ O(1) space - fixed alphabet size
✓ No simulation needed
✓ Direct mathematical calculation
✓ Handles all cases correctly
Perfect! Can't do better than O(n)! ✨
📊 Approach Comparison - The Complete Growth Journey
┌─────────────┬─────────────┬──────────┬──────────────────────┐
│ Approach │ Time │ Space │ Key Insight │
├─────────────┼─────────────┼──────────┼──────────────────────┤
│ Simulation │ O(time×logk)│ O(k) │ Step by step │
│ Math │ O(n) │ O(1) │ Direct formula │
└─────────────┴─────────────┴──────────┴──────────────────────┘
THE COMPLETE LEARNING PROGRESSION:
Level 1: Simulation
Thought: "Simulate each time unit"
Works? YES ✓
Optimal? NO ✗
Time: O(total_time × log k)
Problem: Slow when total_time is large
Level 2: Pattern Recognition
Observation: "Most frequent task creates structure"
Pattern: "Chunks of (n+1) slots"
Formula emerges!
Level 3: Mathematical Insight
Understanding: "(maxFreq-1) chunks + final"
Formula: (maxFreq-1)×(n+1) + countMax
But: Need max with total_tasks!
Level 4: Complete Understanding
WHY max?: Two constraints
- Cooldown: formula_time
- All tasks: total_tasks
Take maximum of both! ✓
Level 5: Optimal Solution
Implementation: Count + formula
Result: O(n) time, O(1) space ✓
Perfect: Can't be better! ✨
Growth: Learned pattern → formula optimization!
CONCRETE EXAMPLE:
Simulation: tasks = 1000 A's, 1 B, n = 2
Total time ≈ 2998
Simulate 2998 time units
Each unit: heap operations
Time: O(2998 × log 2) ≈ 3000 ops
Math Formula:
maxFreq = 1000
countMax = 1
Formula: (1000-1)×(2+1) + 1 = 2998
Time: O(1001) to count
3000x faster for counting! 🚀
💡 Key Learnings - Your Complete Growth
WHAT YOU LEARNED:
1. SIMULATION TO PATTERN:
✓ Start with simulation to understand
✓ Observe pattern: most frequent determines structure
✓ Pattern → mathematical formula!
2. FORMULA DERIVATION:
✓ (maxFreq - 1): Number of intervals
✓ (n + 1): Chunk size
✓ countMax: Final row size
✓ Each piece has clear meaning!
3. WHY MAX WITH TOTAL:
✓ Formula: minimum due to cooldown
✓ Total: minimum to execute all
✓ Must satisfy BOTH constraints!
✓ MAX ensures both are met!
4. EDGE CASES:
✓ n = 0: No cooldown → total_tasks
✓ All same task: Formula dominates
✓ Many varied tasks: total dominates
✓ Formula handles all!
5. OPTIMIZATION TECHNIQUE:
✓ Simulation → Pattern → Formula
✓ Common in scheduling problems
✓ Look for structure in problem!
INTERVIEW STRATEGY:
Progressive Presentation:
"I see two approaches:
Approach 1: Simulation with heap
- Track cooldown for each task
- Use max-heap to pick most frequent
- Time: O(total_time × log k)
- Works but slow for large times
Approach 2: Mathematical formula
- Key insight: most frequent task creates structure
- Structure: (maxFreq-1) chunks of (n+1) slots
- Plus countMax tasks in final row
- Must also execute all tasks
- Formula: max(formula_time, total_tasks)
Let me derive why this works:
[explain (maxFreq-1), (n+1), countMax]
[explain why max]
Time: O(n), Space: O(1)
This is optimal!"
Shows:
✓ Understanding of simulation
✓ Pattern recognition ability
✓ Mathematical reasoning
✓ Complete formula derivation
✓ Edge case awareness
This is REAL mastery! 🌱→🌳→🏆
⚠️ Common Mistakes
Mistake 1: Forgetting countMax in formula
// ❌ WRONG - Only adds 1 at end
int time = (maxFreq - 1) * (n + 1) + 1;
// ✓ CORRECT - Adds all max freq tasks
int time = (maxFreq - 1) * (n + 1) + countMax;
Mistake 2: Not taking max with total tasks
// ❌ WRONG - Doesn't handle dense packing
return (maxFreq - 1) * (n + 1) + countMax;
// ✓ CORRECT - Ensures all tasks executed
return Math.max(formulaTime, tasks.length);
Mistake 3: Wrong chunk size
// ❌ WRONG - Chunk size is n
int time = (maxFreq - 1) * n + countMax;
// ✓ CORRECT - Chunk size is (n + 1)
int time = (maxFreq - 1) * (n + 1) + countMax;
Mistake 4: Not handling n = 0
// With n = 0, formula gives small value
// But without max(formula, total), would be wrong
// ✓ CORRECT - max handles this
return Math.max(formulaTime, tasks.length);
🎯 Pattern Recognition
Problem Type: Scheduling with Constraints
Core Pattern: Greedy + Math Formula
When to Apply:
✓ Scheduling with cooldown/constraints
✓ Minimize time with restrictions
✓ Pattern in optimal arrangement
✓ Most frequent determines structure
Recognition Keywords:
- "schedule"
- "cooldown"
- "minimum time"
- "constraints between same"
Similar Problems:
- Rearrange String k Distance Apart (LC 358)
- Reorganize String (LC 767)
- CPU Scheduling variations
Key Components:
┌────────────────────────────────────────────┐
│ Frequency Count: Know task counts │
│ Pattern: Most frequent creates structure │
│ Formula: (maxFreq-1)×(n+1) + countMax │
│ Max: Handle both constraints │
└────────────────────────────────────────────┘
📝 Quick Revision Notes
🎯 Core Concept:
Schedule tasks with cooldown n, minimize time. Most frequent task creates structure: (maxFreq-1) chunks of (n+1) slots + countMax final. Formula handles cooldown constraint, total_tasks handles execution constraint. Return max(formula, total)!
⚡ Quick Implementation:
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Solution {
public int leastInterval(char[] a, int n) {
// return minHeap(a, n);
return math(a, n);
}
private int math(char[] a, int n) {
// step 1: create freq map
HashMap<Character, Integer> freqMap = new HashMap<>();
for (char ch : a) {
freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
}
// step 2: get max frequency
int maxFreq = 0;
for (int freq : freqMap.values()) {
maxFreq = Math.max(maxFreq, freq);
}
// step 3: how many such max freq are there
int countMaxFreq = 0;
for (int freq : freqMap.values()) {
if (freq == maxFreq) {
countMaxFreq++;
}
}
// part 1 - why maxFreq?
// Example: For ['A', 'A', 'A', 'B', 'B'] and n = 2
// A _ _ A _ _ A => can accomodate remaining in
// gaps => (maxFreq - 1) * (n + 1) + 1 (last A) = 5
// in above formula, n + 1 is number of _ plus A
// part 2 - why countMaxFreq?
// Example: For ['A', 'A', 'A', 'B', 'B', 'B'] and n = 2
// A _ _ A _ _ A B => can accomodate remaining in
// gaps => (maxFreq - 1) * (n + 1) + 2 (last A and B)
// where 2 is number of maxFreq elements
// part 3 - scenario
// Example: For ['A', 'A', 'A', 'B', 'B', 'B', 'C', 'D'] and n = 1
// A _ A _ A B
// (maxFreq - 1) * n + 2 = 2 + 2 = 4 (WRONG) => where we
// will accomodate C and D
// Hence consider all elements also
// Max (part1, len(array)) => max(4, 8) => 8
return Math.max((maxFreq - 1) * (n + 1) + countMaxFreq, a.length);
}
private int minHeap(char[] a, int n) {
// step 1: create freq map
HashMap<Character, Integer> freqMap = new HashMap<>();
for (char ch : a) {
freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
}
// step 2: need 1 PQ and 1 normal queue
// 1. tasks PQ: tasks remaining along with freq (when polled we need
// to get max freq task by that time because its intuitive that max
// freq task should be completed as early as possible or picked up
// or given priority so that we will get benefit in cooldown periods)
// We just need frequencies to be added in PQ. No need of chars as we
// do not use them anywhere while processing.
// 2. cooldown queue: tasks which are in cooldown period
// once task from tasks PQ is executed, we have to push that task to cooldown
// period by reducing its frequency. At the start of each time tick, we have to
// check if any task in this cooldown queue is awaiting for the task exeuction
// post its cooldown. If yes, we need to move it to tasks PQ and then we will
// get task picked now consolidately for all tasks which comepleted cooldown
// also.
// Note: this cooldown queue does not need to be a PQ because all tasks in this
// queue are based out of time period and task will come up once cooldown done.
PriorityQueue<Integer> tasks = new PriorityQueue<>(Comparator.reverseOrder());
Queue<int[]> cooldown = new LinkedList<>();
// step 3: put all frequencies in tasks PQ
tasks.addAll(freqMap.values());
// step 4: start timer
int timer = 0;
while (!tasks.isEmpty() || !cooldown.isEmpty()) {
// step 5: check if any task post cooldown is waiting.
// If yes, add it to tasks queue
if (!cooldown.isEmpty() && cooldown.peek()[1] == timer) {
tasks.offer(cooldown.poll()[0]);
}
// step 6: process if any task is available
if (!tasks.isEmpty()) {
int freq = tasks.poll() - 1;
if (freq > 0) {
cooldown.offer(new int[] { freq, timer + n + 1 });
}
}
timer++;
}
return timer;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.leastInterval(new char[] { 'A', 'A', 'A', 'B', 'B', 'B' }, 2)); // 8
System.out.println(s.leastInterval(new char[] { 'A', 'C', 'A', 'B', 'D', 'B' }, 1)); // 6
System.out.println(s.leastInterval(new char[] { 'A', 'A', 'A', 'B', 'B', 'B' }, 3)); // 10
}
}
🔑 Key Insights:
- (maxFreq - 1): Number of intervals between first and last
- (n + 1): Chunk size (1 task + n cooldown)
- countMax: All tasks with max frequency in final row
- max(formula, total): Two constraints to satisfy
- Why max?: Cooldown vs execution constraint
- Time: O(n), Space: O(1) - optimal! ✓
🎪 Memory Aid:
"Most frequent creates chunks!"
"(max-1) chunks of (n+1) + count!"
"Max of formula and total tasks!" ✨
🧪 Edge Cases
Case 1: n = 0 (no cooldown)
tasks = ["A","A","A"], n = 0
Formula: (3-1)×1 + 1 = 3
Total: 3
Result: max(3, 3) = 3 ✓
Case 2: All different tasks
tasks = ["A","B","C"], n = 100
Formula: (1-1)×101 + 3 = 3
Total: 3
Result: max(3, 3) = 3 ✓
No cooldown issue!
Case 3: All same task
tasks = ["A","A","A","A"], n = 2
Formula: (4-1)×3 + 1 = 10
Total: 4
Result: max(10, 4) = 10 ✓
Lots of idle!
All handled correctly! ✓
🎓 Complexity Analysis
Approach 1: Simulation
Time: O(total_time × log k)
total_time ≈ tasks.length in best case
Each time unit: heap operations O(log k)
k = unique tasks ≤ 26
Space: O(k)
Heap + queue
Approach 2: Math Formula
Time: O(n)
Count frequencies: O(n)
Find max: O(26) = O(1)
Count max: O(26) = O(1)
Formula: O(1)
Total: O(n)
Space: O(1)
Fixed array size 26
Optimal! Can't do better!
Happy practicing! 🎯
Note: This problem is BRILLIANT for learning pattern → formula optimization! You start with simulation (works but slow), observe the pattern (most frequent creates structure), then derive the mathematical formula. The formula derivation is BEAUTIFUL: (maxFreq-1) intervals × (n+1) chunk size + countMax final tasks. Understanding WHY we need max(formula, total) - two constraints that must both be satisfied - is KEY. This teaches you to look for mathematical patterns in scheduling problems rather than brute force simulation. The jump from O(total_time × log k) to O(n) is HUGE! True algorithmic growth! 💪✨🏆