DSA
Task Scheduler
Three approaches — Math formula O(n), Greedy Max-Heap O(n log k), Sorted Array O(n). Find minimum CPU intervals with cooldown constraint.
Key insighttry it first, then reveal
The bottleneck is always the most frequent task. It forces the schedule's skeleton — everything else fills in around it.
Given an array of CPU tasks labeled A–Z and a cooldown n, return the minimum number of CPU intervals to finish all tasks. Between two tasks with the same label there must be at least n idle or different-task intervals.
Practice Link
Intuition#
The bottleneck is always the most frequent task. It forces the schedule's skeleton — everything else fills in around it.
Visualise the schedule as a frame of slots:
n = 2, tasks = [A×3, B×3]
Frame: [ A B _ ] ← n+1 = 3 slots per row
[ A B _ ]
[ A B ] ← last row: only maxCount tasks, no trailing idle
- There are maxFreq - 1 full rows, each of size n+1.
- The last row has maxCount tasks (all tasks tied at max frequency).
- Total = (maxFreq - 1) × (n+1) + maxCount
- But if tasks are dense enough to fill every slot, no idle is ever needed — the answer is simply tasks.size().
So: max(tasks.size(), (maxFreq - 1) × (n+1) + maxCount)
Approach 1 — Math Formula#
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26, 0);
for (char c : tasks) freq[c - 'A']++;
int maxFreq = *max_element(freq.begin(), freq.end()) // find max frequency
int maxCount = count(freq.begin(), freq.end(), maxFreq) // find number of tasks with max frequency;
return max((int)tasks.size(), (maxFreq - 1) * (n + 1) + maxCount);
}
};
Time: O(n) — one pass to count, one pass to find max
Space: O(1) — fixed 26-element array
Verify on examples:
| tasks | n | maxFreq | maxCount | formula | tasks.size() | answer |
|---|---|---|---|---|---|---|
| A×3, B×3 | 2 | 3 | 2 | (2)×3+2 = 8 | 6 | 8 ✓ |
| A×3, B×3 | 3 | 3 | 2 | (2)×4+2 = 10 | 6 | 10 ✓ |
| A×2,B×2,C×1,D×1 | 1 | 2 | 2 | (1)×2+2 = 4 | 6 | 6 ✓ |
The third example shows why we take max — when tasks are dense (many distinct types), no idling is needed and tasks.size() wins.
Approach 2 — Greedy Max-Heap#
Always execute the most-frequent remaining task first. Process in cycles of n+1 slots. After each cycle, push surviving tasks back and add the elapsed time.
- Last cycle: add only taskCount (no trailing idle after the final task).
- Any other cycle: add n+1 (must serve the full cooldown window, idle or not).
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26, 0);
for (char c : tasks) freq[c - 'A']++;
priority_queue<int> pq;
for (int i = 0; i < 26; i++)
if (freq[i] > 0) pq.push(freq[i]);
int time = 0;
while (!pq.empty()) {
int cycle = n + 1;
vector<int> store;
int taskCount = 0;
while (cycle-- && !pq.empty()) {
if (pq.top() > 1) store.push_back(pq.top() - 1);
pq.pop();
taskCount++;
}
for (int x : store) pq.push(x);
// last cycle: add only tasks executed (no trailing idle)
// mid cycle: add n+1 (full cooldown window, idle slots included)
time += pq.empty() ? taskCount : n + 1;
}
return time;
}
};
Time: O(n log k) where k = distinct task types ≤ 26 → effectively O(n)
Space: O(k) = O(1)
Trace — tasks = [A×3, B×3], n = 2:
| Cycle | Tasks executed | taskCount | pq after | time added | total |
|---|---|---|---|---|---|
| 1 | A(3→2), B(3→2), idle | 2 | [2,2] | n+1 = 3 | 3 |
| 2 | A(2→1), B(2→1), idle | 2 | [1,1] | n+1 = 3 | 6 |
| 3 | A(1→done), B(1→done) | 2 | [] | taskCount = 2 | 8 ✓ |
Approach 3 — Greedy with Sorted Array#
Same greedy logic as the heap but sorts the 26-element array each cycle instead. Since the array is fixed at 26 elements, sorting is O(26 log 26) = O(1) per cycle.
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26, 0);
for (char c : tasks) freq[c - 'A']++;
sort(freq.rbegin(), freq.rend());
int time = 0;
while (freq[0] > 0) {
int i = 0;
// execute up to n+1 most frequent tasks
while (i <= n) {
if (i < 26 && freq[i] > 0) freq[i]--;
time++;
i++;
// stop early only if all tasks done
if (freq[0] == 0) break;
}
sort(freq.rbegin(), freq.rend());
}
return time;
}
};
Time: O(n × 26 log 26) = O(n)
Space: O(1)
This is the most verbose of the three — the math formula is preferred for interviews.
Comparison#
| Approach | Time | Space | Best for |
|---|---|---|---|
| Math Formula | O(n) | O(1) | Interviews — cleanest insight |
| Greedy Max-Heap | O(n log k) | O(k) | When you need to know the actual schedule |
| Greedy Sorted Array | O(n) | O(1) | Avoids heap but more code |
The math formula is the most elegant: recognise that the answer is either the formula-based frame size or the raw task count — whichever is larger.