Task Scheduler [Medium] — Greedy Frequency Buckets

Problem Statement

Given a char array tasks (A-Z) and a cooldown integer n, find the minimum number of intervals to finish all tasks (each interval = 1 unit). Same task must be at least n apart.

Input: tasks=["A","A","A","B","B","B"], n=2 → Output: 8

Intuition

The bottleneck is the most frequent task. Arrange it in (n+1) slots creating a "frame" and fill gaps. Formula:

max((maxCount-1)*(n+1) + numTasksWithMaxCount, tasks.length)

Solutions

C++

int leastInterval(vector<char>& tasks, int n) {
    int freq[26]={};
    for (char c:tasks) freq[c-'A']++;
    int maxCount=*max_element(freq,freq+26);
    int numMax=count(freq,freq+26,maxCount);
    return max((int)tasks.size(), (maxCount-1)*(n+1)+numMax);
}

Java

public int leastInterval(char[] tasks, int n) {
    int[] freq=new int[26];
    for (char c:tasks) freq[c-'A']++;
    int maxCount=0; for (int f:freq) maxCount=Math.max(maxCount,f);
    int numMax=0; for (int f:freq) if(f==maxCount) numMax++;
    return Math.max(tasks.length,(maxCount-1)*(n+1)+numMax);
}

JavaScript

var leastInterval = function(tasks, n) {
    const freq=new Array(26).fill(0);
    for (const c of tasks) freq[c.charCodeAt(0)-65]++;
    const maxCount=Math.max(...freq);
    const numMax=freq.filter(f=>f===maxCount).length;
    return Math.max(tasks.length,(maxCount-1)*(n+1)+numMax);
};

Python

from collections import Counter

def leastInterval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    max_count = max(counts.values())
    num_max = sum(1 for v in counts.values() if v == max_count)
    return max(len(tasks), (max_count - 1) * (n + 1) + num_max)

Complexity

Time: O(n)
Space: O(1)