CPU Task Scheduler
Mahabharata — Drona's Battle Plan — Scheduling Warrior Tasks with Mandatory Rest Periods
n-काल प्रतीक्षा — समान कार्य पुनः न करें। सबसे व्यस्त पहले — ढेर से चुनो चक्र-चक्र॥
*n-time cooldown — same task cannot repeat. Pick busiest first — from heap, cycle by cycle.*
The Story
Given a list of CPU tasks and a cooldown n, find the minimum time to execute all tasks. Same task cannot be executed within n intervals of each other; idle slots fill the gap.
For `tasks=[A,A,A,B,B,B]`, n=2: ABAB_A_B or ABABAB → answer=8.
**Max-Heap Simulation:** - Count task frequencies. Max-heap by frequency. - Each cycle: pick up to n+1 most frequent tasks (one per slot, all different). Execute, decrement count, push back if > 0. - If cycle has fewer than n+1 tasks: remaining slots are idle.
```java int[] freq = new int[26]; for (char c : tasks) freq[c-'A']++; PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a); for (int f : freq) if (f > 0) pq.offer(f); int time = 0; while (!pq.isEmpty()) { List<Integer> temp = new ArrayList<>(); int k = n + 1; while (k-- > 0 && !pq.isEmpty()) { temp.add(pq.poll() - 1); } for (int t : temp) if (t > 0) pq.offer(t); time += pq.isEmpty() ? temp.size() : n + 1; // If done, no idle; else full cycle } ```
**Formula alternative:** time = max(tasks.length, (maxFreq-1)*(n+1) + countOfMaxFreq). But the heap simulation is more general and intuitive.
Trace `[A,A,A,B,B,B]`, n=2: - freq: A=3, B=3. pq=[3,3] - Cycle1: poll 3,3 → temp=[2,2]. Push back. time=3 (n+1=3) - Cycle2: poll 2,2 → temp=[1,1]. Push back. time=6 - Cycle3: poll 1,1 → temp=[0,0]. Nothing pushed back. pq empty. time += temp.size()=2. Total=8 ✓
The Formula Approach
time = max(n_tasks, (maxFreq-1)*(n+1) + countMaxFreq). O(n) but doesn't simulate.
public int leastIntervalFormula(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c-'A']++;
Arrays.sort(freq);
int maxFreq = freq[25], count = 0;
for (int f : freq) if (f == maxFreq) count++;
return Math.max(tasks.length, (maxFreq-1)*(n+1) + count);
}Drona's Greedy Cycle Wisdom
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int f : freq) if (f > 0) pq.offer(f);
int time = 0;
while (!pq.isEmpty()) {
List<Integer> temp = new ArrayList<>();
int k = n + 1;
while (k-- > 0 && !pq.isEmpty()) {
temp.add(pq.poll() - 1);
}
for (int t : temp) if (t > 0) pq.offer(t);
time += pq.isEmpty() ? temp.size() : n + 1;
}
return time;
}Step-by-Step Walkthrough
[A,A,A,A], n=2 pq=[4]. Cycle1: poll 4→3, push 3. time=3. Cycle2: poll 3→2, push 2. time=6. Cycle3: poll 2→1, push 1. time=9. Cycle4: poll 1→0, no push. pq empty → time+=1. Total=10. A__A__A__A = 10 ✅
Deep Insight
**The formula vs simulation:** - Formula `max(tasks.length, (maxFreq-1)*(n+1) + countMaxFreq)` gives the answer directly but only works for this specific problem. - Simulation with heap is more general and shows the actual scheduling.
**Why greedily pick the most frequent?** The most frequent tasks are the bottleneck — they create the most idle time. By scheduling them first in each cycle, we minimize the total idle slots.
**Cycle boundary:** If heap becomes empty mid-cycle (all tasks done), we don't add idle time for the remaining slots — `time += temp.size()` not `n+1`.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log 26) = O(n) | O(26) = O(1) | Formula: O(n) count + O(1) compute |
| Optimal | O(n log 26) = O(n) | O(26) = O(1) | 26 task types at most; heap bounded by 26 |
Pattern Recognition
✅ CPU scheduling with cooldown → greedy max-heap simulation ✅ Cycle of size n+1; pick most frequent tasks each cycle ✅ If heap empty mid-cycle: time += actual slots (no idle) ✅ Formula shortcut: max(n_tasks, (maxFreq-1)*(n+1) + countMax) **LeetCode Trigger Phrases:** → "task scheduler" with cooldown n → Minimum time with frequency-based scheduling → Greedy cycle scheduling
Bhagavad Gita 3.8
नियतं कुरु कर्म त्वं कर्म ज्यायो ह्यकर्मणः। शरीरयात्रापि च ते न प्रसिद्ध्येदकर्मणः॥
Perform your prescribed duty, for action is superior to inaction. Even the maintenance of your body would not be possible through inaction.
Connection: The CPU cannot remain idle when there is useful work to be done — yet it must respect the cooldown between same tasks. The scheduler greedily assigns the most critical tasks first each cycle, ensuring constant productivity while honoring necessary intervals. Like the Gita's call to continuous prescribed action over inaction, the scheduler minimizes idle time by always doing the next most important task available.