Problem Statement:
You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there’s a constraint: there has to be a gap of at least n intervals between two tasks with the same label.
Return the minimum number of CPU intervals required to complete all tasks.
Example 1:
Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.
Example 2:
Input: [“A”,”C”,”A”,”B”,”D”,”B”], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B. With a cooling interval of 1, you can repeat a task after just one other task.
Example 3:
Input: tasks = [“A”,”A”,”A”, “B”,”B”,”B”], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B. There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.
Constraints
1 <= tasks.length <= 104tasks[i]is an uppercase English letter.0 <= n <= 100
Approach:
- Count frequency of each task (A–Z).
- Find the maximum frequency
(maxFreq)— the most repeated task. - Count how many tasks have this maximum frequency (countOfMaxFreqCharacters).
- Compute the ideal cycles needed to schedule these most frequent tasks with cooldowns:
(n+1)×(maxFreq−1)+countOfMaxFreqCharacters
(n+1)→ each group of task + cooldown.(maxFreq - 1)→ groups formed except last one.countOfMaxFreqCharacters→ handles ties of max frequency tasks
- The result is the maximum of:
arr.length(if enough tasks to fill gaps)cycles(if idle slots are unavoidable)
Time & Space Complexity:
Time Complexity: O(arr.length)
Space Complexity: O(1)
Dry Run
Input: arr = ["A","A","A","B","B","B"], n = 2
Step 0: Start Function: leastInterval(arr, n) arr = ["A","A","A","B","B","B"], n = 2 freq = Array(26).fill(0) // all zeros maxFreq = 0 Step 1: Build frequency table and track maxFreq i = 0, arr[0] = "A" -> curr = "A".charCodeAt() - 65 = 0 ++freq[0] => freq['A'] = 1 maxFreq = max(0,1) = 1 i = 1, arr[1] = "A" ++freq[0] => freq['A'] = 2 maxFreq = max(1,2) = 2 i = 2, arr[2] = "A" ++freq[0] => freq['A'] = 3 maxFreq = max(2,3) = 3 i = 3, arr[3] = "B" -> curr = 1 ++freq[1] => freq['B'] = 1 maxFreq = max(3,1) = 3 i = 4, arr[4] = "B" ++freq[1] => freq['B'] = 2 maxFreq = max(3,2) = 3 i = 5, arr[5] = "B" ++freq[1] => freq['B'] = 3 maxFreq = max(3,3) = 3 After loop: freq['A'] = 3, freq['B'] = 3, all others = 0 maxFreq = 3 Step 2: Count how many characters have frequency == maxFreq countOfMaxFreqCharacters = 0 for i from 0..25: when i=0 (A): freq[0] === 3 -> ++countOfMaxFreqCharacters => 1 when i=1 (B): freq[1] === 3 -> ++countOfMaxFreqCharacters => 2 others: freq != 3 Final countOfMaxFreqCharacters = 2 Step 3: Compute cycles (minimum length by the formula) cycles = ((n + 1) * (maxFreq - 1)) + countOfMaxFreqCharacters = ((2 + 1) * (3 - 1)) + 2 = (3 * 2) + 2 = 6 + 2 = 8 Step 4: Final result is max(arr.length, cycles) arr.length = 6 cycles = 8 return Math.max(6, 8) => 8 Step 5: End Final returned value = 8
Output: 8
var leastInterval = function(tasks, n) {
let freq = Array(26).fill(0);
let maxFreq = 0;
for (let i = 0; i < tasks.length; i++) {
let curr = tasks[i].charCodeAt() - 65; // Map 'A'-'Z' to 0-25
freq[curr]++;
maxFreq = Math.max(maxFreq, freq[curr]);
}
let countMaxFreq = 0;
for (let i = 0; i < 26; i++) {
if (freq[i] === maxFreq) {
countMaxFreq++;
}
}
let cycles = (maxFreq - 1) * (n + 1) + countMaxFreq;
return Math.max(tasks.length, cycles);
};
def leastInterval(tasks, n):
freq = [0] * 26
maxFreq = 0
for t in tasks:
c = t[0] # in case it's a string
idx = ord(c) - ord('A')
freq[idx] += 1
if freq[idx] > maxFreq:
maxFreq = freq[idx]
countOfMax = sum(1 for f in freq if f == maxFreq)
cycles = (n + 1) * (maxFreq - 1) + countOfMax
return max(len(tasks), cycles)
import java.util.*;
public class Main {
public static int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
int maxFreq = 0;
for (char c : tasks) {
int idx = c - 'A';
freq[idx]++;
if (freq[idx] > maxFreq) maxFreq = freq[idx];
}
int countOfMax = 0;
for (int f : freq) if (f == maxFreq) countOfMax++;
int cycles = (n + 1) * (maxFreq - 1) + countOfMax;
return Math.max(tasks.length, cycles);
}
public static void main(String[] args) {
char[] tasks = {'A','A','A','B','B','B'};
int n = 2;
System.out.println(leastInterval(tasks, n)); // expected 8
}
}
#include <bits/stdc++.h>
using namespace std;
int leastInterval(const vector& tasks, int n) {
vector freq(26, 0);
int maxFreq = 0;
for(char c : tasks) {
int idx = c - 'A';
++freq[idx];
maxFreq = max(maxFreq, freq[idx]);
}
int countOfMax = 0;
for(int f : freq) if(f == maxFreq) ++countOfMax;
int cycles = (n + 1) * (maxFreq - 1) + countOfMax;
return max((int)tasks.size(), cycles);
}
int main() {
vector tasks = {'A','A','A','B','B','B'};
int n = 2;
cout << leastInterval(tasks, n) << endl; // expected 8
return 0;
}
#include <stdio.h>
#include <string.h>
int leastInterval(char tasks[][2], int tasksSize, int n) {
int freq[26];
for(int i=0;i<26;i++) freq[i]=0;
int maxFreq = 0;
for(int i=0;i maxFreq) maxFreq = freq[idx];
}
int countOfMax = 0;
for(int i=0;i<26;i++) if(freq[i] == maxFreq) ++countOfMax;
int cycles = (n + 1) * (maxFreq - 1) + countOfMax;
return (tasksSize > cycles) ? tasksSize : cycles;
}
int main() {
char tasks[][2] = {"A","A","A","B","B","B"};
int size = sizeof(tasks) / sizeof(tasks[0]);
int n = 2;
printf("%d\n", leastInterval(tasks, size, n));
return 0;
}
using System;
using System.Collections.Generic;
class Program {
static int LeastInterval(char[] tasks, int n) {
int[] freq = new int[26];
int maxFreq = 0;
foreach(char c in tasks) {
int idx = c - 'A';
freq[idx]++;
if (freq[idx] > maxFreq) maxFreq = freq[idx];
}
int countOfMax = 0;
foreach(int f in freq) if (f == maxFreq) countOfMax++;
int cycles = (n + 1) * (maxFreq - 1) + countOfMax;
return Math.Max(tasks.Length, cycles);
}
static void Main() {
char[] tasks = new char[] {'A','A','A','B','B','B'};
int n = 2;
Console.WriteLine(LeastInterval(tasks, n)); // expected 8
}
}
