Task Scheduler

medium array heap greedy

Problem

Given a list of task labels and a non-negative cooldown n, find the minimum number of time slots needed. Identical tasks must be at least n slots apart; idle slots are allowed.

Inputtasks = ["A","A","A","B","B","B"], n = 2

Output8

A B idle A B idle A B → 8 slots. Closed-form: max(len(tasks), (max-1)·(n+1) + (#tasks tied for max)).

tasks (e.g. A,A,A,B,B,B)

cooldown n

from collections import Counter
def least_interval(tasks, n):
    counts = Counter(tasks)
    max_freq = max(counts.values())
    ties = sum(1 for v in counts.values() if v == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + ties)

function leastInterval(tasks, n) {
  const counts = new Map();
  for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
  let maxFreq = 0;
  for (const v of counts.values()) maxFreq = Math.max(maxFreq, v);
  let ties = 0;
  for (const v of counts.values()) if (v === maxFreq) ties++;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + ties);
}

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char c : tasks) counts[c - 'A']++;
        int maxFreq = 0;
        for (int v : counts) maxFreq = Math.max(maxFreq, v);
        int ties = 0;
        for (int v : counts) if (v == maxFreq) ties++;
        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + ties);
    }
}

int leastInterval(vector<char>& tasks, int n) {
    int counts[26] = {};
    for (char c : tasks) counts[c - 'A']++;
    int maxFreq = *max_element(counts, counts + 26);
    int ties = 0;
    for (int v : counts) if (v == maxFreq) ties++;
    return max((int)tasks.size(), (maxFreq - 1) * (n + 1) + ties);
}

Explanation

Instead of simulating slot by slot, this solution uses a neat counting formula. The total time is driven entirely by the most frequent task, because that task forces the most waiting around due to the cooldown.

Picture the most frequent task, which appears max_freq times. It splits the timeline into max_freq - 1 gaps, and each gap must be at least n + 1 slots wide (the task plus its cooldown). That skeleton takes (max_freq - 1) * (n + 1) slots, and then we add ties for the final block: the number of tasks that also reach the maximum frequency.

But if there are lots of different tasks, the gaps fill up naturally and no idle time is needed. In that case the answer is just the total number of tasks. So we take the max of the formula and len(tasks).

Example: tasks = ["A","A","A","B","B","B"], n = 2. Here max_freq = 3 and two tasks tie at 3, so the formula gives (3 - 1) * (2 + 1) + 2 = 8. Since len(tasks) = 6 is smaller, the answer is 8 (for example A B _ A B _ A B).

This works because the busiest task is the real bottleneck, and any leftover tasks either slot neatly into the gaps or simply lengthen the timeline.

Time: O(n + 26) Space: O(26)