Log inSign up
mediumLeetCodeNot Started

Task Scheduler

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

Given a character array tasks representing CPU tasks where each letter represents a unique task, and a cooldown period n between two identical tasks.

Each task takes 1 unit of time to complete. In each time unit, the CPU can either execute one task or remain idle.

Return the least number of units of time that the CPU will take to finish all given tasks.

Example 1 · Example 1: Forced Idles:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: Schedule: A -> B -> idle -> A -> B -> idle -> A -> B.\nTotal time = 8 units.

Example 2 · Example 2: No Idles Needed:

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: Schedule: A -> B -> C -> D -> A -> B (no idles needed, total time = tasks.length = 6).

Constraints:

  • 1 <= tasks.length <= 104
  • tasks[i] is an uppercase English letter.
  • 0 <= n <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Derive the idle slot filling formula for interval scheduling with cooling periods.
  • Understand why high-frequency tasks determine the schedule lower bound.
  • Implement the optimal O(N) solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • CPU task scheduling with cooling period between identical tasks.
  • Minimizing total time including forced idle periods.
  • Task frequency dominance.

Algorithmic Decision Tree:

  • Count frequencies of all tasks.
  • Find maxFreq and how many tasks share maxFreq.
  • Compute max(tasks.length, (maxFreq - 1) * (n + 1) + countMaxFreq).

Connected Patterns:

Reorganize StringRearrange String k Distance ApartJob Sequencing Problem

1. Cycle-by-Cycle Greedy Simulation

Intuition

Simulate each CPU cycle. Track available cooldown for each task and greedily execute the task with highest remaining frequency.

Algorithm

  1. Step 1: Count frequency of each task.
  2. Step 2: Maintain nextAvailable time array of size 26 initialized to 0.
  3. Step 3: In each time cycle: find available task with maximum remaining frequency.
  4. Step 4: If found: decrement frequency, set nextAvailable = time + n + 1.
  5. Step 5: Increment time and repeat until all task frequencies are 0.
  6. Step 6: Return time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int leastInterval(vector<char>& tasks, int n) {
10 vector<int> count(26, 0);
11 for (char c : tasks) count[c - 'A']++;
12
13 vector<int> nextAvail(26, 0);
14 int totalTasks = tasks.size();
15 int time = 0;
16
17 while (totalTasks > 0) {
18 int best = -1;
19 for (int i = 0; i < 26; ++i) {
20 if (count[i] > 0 && nextAvail[i] <= time) {
21 if (best == -1 || count[i] > count[best]) {
22 best = i;
23 }
24 }
25 }
26
27 if (best != -1) {
28 count[best]--;
29 nextAvail[best] = time + n + 1;
30 totalTasks--;
31 }
32 time++;
33 }
34
35 return time;
36 }
37};
38
39int main() {
40 Solution sol;
41 vector<char> tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
42 int n = 2;
43 cout << "Least Intervals: " << sol.leastInterval(tasks, n) << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(Total Time * 26)
  • Space complexity: O(26)

2. Max-Heap + Cooldown Queue

Intuition

Maintain ready tasks in a max-heap and cooling tasks in a queue of pairs (count, readyTime). In each cycle, pop highest frequency task and enqueue until ready.

Algorithm

  1. Step 1: Count task frequencies and insert non-zero counts into a max-heap.
  2. Step 2: Maintain a cooldown queue holding pairs [count, availableTime].
  3. Step 3: In each time unit: if queue front is ready (queue.peek()[1] == time), push back into max-heap.
  4. Step 4: If heap is not empty: pop task, decrement count; if count > 0, push to queue with time + n + 1.
  5. Step 5: Increment time.
  6. Step 6: Return time when both heap and queue are empty.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7class Solution {
8public:
9 int leastInterval(vector<char>& tasks, int n) {
10 vector<int> counts(26, 0);
11 for (char c : tasks) counts[c - 'A']++;
12
13 priority_queue<int> maxHeap;
14 for (int c : counts) {
15 if (c > 0) maxHeap.push(c);
16 }
17
18 queue<pair<int, int>> waitQueue; // {count, availableTime}
19 int time = 0;
20
21 while (!maxHeap.empty() || !waitQueue.empty()) {
22 time++;
23
24 if (!maxHeap.empty()) {
25 int count = maxHeap.top();
26 maxHeap.pop();
27 if (count - 1 > 0) {
28 waitQueue.push({count - 1, time + n});
29 }
30 }
31
32 if (!waitQueue.empty() && waitQueue.front().second == time) {
33 maxHeap.push(waitQueue.front().first);
34 waitQueue.pop();
35 }
36 }
37
38 return time;
39 }
40};
41
42int main() {
43 Solution sol;
44 vector<char> tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
45 int n = 2;
46 cout << "Least Intervals (Heap): " << sol.leastInterval(tasks, n) << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(Total Time * log 26)
  • Space complexity: O(26)

3. Greedy Frequency Slot Partitioning

Intuition

Calculate max frequency and count of tasks sharing max frequency. Compute slots required using the mathematical formula max(totalTasks, (maxFreq - 1) * (n + 1) + countMaxFreq).

Algorithm

  1. Step 1: Count frequencies of all tasks in an array of size 26.
  2. Step 2: Find maxFreq = maximum frequency across all tasks.
  3. Step 3: Count how many tasks have frequency == maxFreq (countMaxFreq).
  4. Step 4: Formula base = (maxFreq - 1) * (n + 1) + countMaxFreq.
  5. Step 5: Return max(tasks.length, base).

Interactive Trace for Task Scheduler

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Chunk 1 layout: Place 'A' and 'B' followed by 1 idle slot (cooldown = 2)
Visual state
Values and pointers at this exact step
pointers
S
exec
exec
idle
0
↑ chunk 1
1
2
Check / comparison
Chunk 1 of size n + 1 = 3
Decision / next transition
Time consumed: 3 units.
Why this step matters

Step 1: Chunk 1 layout: Place A and B followed by 1 idle slot (cooldown = 2). [A, B, idle].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int leastInterval(vector<char>& tasks, int n) {
10 vector<int> freq(26, 0);
11 for (char c : tasks) freq[c - 'A']++;
12
13 int maxFreq = 0;
14 for (int f : freq) maxFreq = max(maxFreq, f);
15
16 int countMaxFreq = 0;
17 for (int f : freq) {
18 if (f == maxFreq) countMaxFreq++;
19 }
20
21 int minTime = (maxFreq - 1) * (n + 1) + countMaxFreq;
22 return max((int)tasks.size(), minTime);
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<char> tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
29 int n = 2;
30 cout << "Least Intervals (Optimal): " << sol.leastInterval(tasks, n) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Simulation with Cooldown MapO(Total Time * 26)O(26)Simulate each CPU cycle. Among tasks available (not in cooldown), pick the one with highest remaining frequency. If none available, spend an idle cycle.Step-by-step cycle simulation.
2.Better — Max-Heap + Wait Queue SimulationO(Total Time * log 26)O(26)Maintain task frequencies in a max-heap and cooling tasks in a wait queue (count, availableTime). In each cycle, pop highest frequency task and enqueue until available.Heap pushing and popping.
3.Optimal — Greedy Slot Math FormulaOptimalO(N)O(1) auxiliaryCount frequencies of characters in O(N). Find max frequency and tasks sharing it. Return max(N, (maxFreq - 1) * (n + 1) + countMaxFreq).Frequency counting.
Back to DSA Sheet