# Task Scheduler

- **Canonical ID**: `task-scheduler`
- **Canonical URL**: https://dsacheatsheet.com/problems/task-scheduler
- **Difficulty**: medium
- **Patterns**: Heaps, Greedy
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/task-scheduler/

## 1. Core Invariant / The Trick

Most frequent task (`maxFreq` occurring `maxCount` times) dictates frame geometry: `(maxFreq - 1)` full chunks of length `(n + 1)`, plus a final partial frame of `maxCount` tasks. If non-max tasks fill all idle slots, total time simply equals `len(tasks)`: `max(len(tasks), (maxFreq - 1) * (n + 1) + maxCount)`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(T)`
- **Space Complexity**: `O(1)`
- **Proof**: 26 uppercase task labels take O(1) auxiliary frequency storage; frequency counting and closed-form evaluation run in one linear pass.

## 3. Minimal Idiomatic Code

### Python
```python
def leastInterval(tasks: list[str], n: int) -> int:
    freq = [0] * 26
    for t in tasks:
        freq[ord(t) - 65] += 1
    max_f = max(freq)
    max_cnt = freq.count(max_f)
    return max(len(tasks), (max_f - 1) * (n + 1) + max_cnt)
```

### TypeScript
```typescript
export function leastInterval(tasks: string[], n: number): number {
  const freq = new Array(26).fill(0);
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
  const maxF = Math.max(...freq);
  const maxCnt = freq.filter((f) => f === maxF).length;
  return Math.max(tasks.length, (maxF - 1) * (n + 1) + maxCnt);
}
```

### C++
```cpp
int leastInterval(vector<char>& tasks, int n) {
    int freq[26] = {0}, maxF = 0, maxCnt = 0;
    for (char c : tasks) maxF = max(maxF, ++freq[c - 'A']);
    for (int f : freq) if (f == maxF) maxCnt++;
    return max((int)tasks.size(), (maxF - 1) * (n + 1) + maxCnt);
}
```

### Java
```java
int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    int maxF = 0, maxCnt = 0;
    for (char c : tasks) maxF = Math.max(maxF, ++freq[c - 'A']);
    for (int f : freq) if (f == maxF) maxCnt++;
    return Math.max(tasks.length, (maxF - 1) * (n + 1) + maxCnt);
}
```

### Go
```go
func leastInterval(tasks []byte, n int) int {
    var freq [26]int
    maxF, maxCnt := 0, 0
    for _, c := range tasks {
        freq[c-'A']++
        if freq[c-'A'] > maxF { maxF = freq[c-'A'] }
    }
    for _, f := range freq { if f == maxF { maxCnt++ } }
    return max(len(tasks), (maxF-1)*(n+1)+maxCnt)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Forgetting `max(len(tasks), formula)` undercounts when extra task types overflow the idle frame width `n + 1`.
- Heap + cooldown queue simulation is O(T log 26) and useful if asked for an explicit schedule sequence.

### Follow-ups
- If asked to emit an actual valid execution order, pair a max-heap with a cooldown FIFO queue `(readyTime, remainingCount, task)`.