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.

September 16, 2026

DSA Heap Priority Queue Greedy LeetCode Practice 🏢 Amazon

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#

cpp

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).

cpp

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.

cpp

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.

DSASort Characters By FrequencyMax-heap on character frequency. Time O(n + d log d), Space O(d) where d = distinct characters.DSAK Closest Points to OriginMax-heap of size k — evict the farthest point on each insert. Time O(n log k), Space O(k).DSAFind Kth RotationBinary Search. Time O(logn), Space O(1).

Intuition#

Approach 1 — Math Formula#

Approach 2 — Greedy Max-Heap#

Approach 3 — Greedy with Sorted Array#

Comparison#

Related articles