LeetCode 621: Task Scheduler (Greedy Counting)
LeetCode 621ArrayGreedyToday we solve LeetCode 621 - Task Scheduler.
Source: https://leetcode.com/problems/task-scheduler/
English
Problem Summary
Given a list of tasks represented by uppercase letters and a cooldown n, each same task must be separated by at least n intervals. Return the minimum intervals needed to finish all tasks.
Key Insight
The bottleneck is the task with highest frequency. If its count is maxFreq, it creates maxFreq - 1 full gaps, and each gap must hold n slots. Tasks tied at max frequency share the last row.
Baseline and Why It Can Be Slower
A max-heap simulation (pick top available tasks cycle by cycle) is valid but introduces heap operations each interval. We can compute answer directly with a counting formula.
Optimal Algorithm (Step-by-Step)
1) Count frequency of 26 task letters.
2) Find maxFreq and maxCount (how many letters have frequency maxFreq).
3) Compute frame length: (maxFreq - 1) * (n + 1) + maxCount.
4) Real answer is max(totalTasks, frameLength).
Complexity Analysis
Time: O(m + 26) where m is number of tasks.
Space: O(26).
Common Pitfalls
- Forgetting to use max(...) with task length when tasks fill all idle slots.
- Miscounting how many tasks tie at the maximum frequency.
- Using wrong frame formula like maxFreq * (n + 1) (off by one block).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;
int maxFreq = 0;
for (int f : freq) maxFreq = Math.max(maxFreq, f);
int maxCount = 0;
for (int f : freq) {
if (f == maxFreq) maxCount++;
}
int frame = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(tasks.length, frame);
}
}func leastInterval(tasks []byte, n int) int {
freq := make([]int, 26)
for _, c := range tasks {
freq[c-'A']++
}
maxFreq := 0
for _, f := range freq {
if f > maxFreq {
maxFreq = f
}
}
maxCount := 0
for _, f := range freq {
if f == maxFreq {
maxCount++
}
}
frame := (maxFreq-1)*(n+1) + maxCount
if len(tasks) > frame {
return len(tasks)
}
return frame
}class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26, 0);
for (char c : tasks) freq[c - 'A']++;
int maxFreq = 0;
for (int f : freq) maxFreq = max(maxFreq, f);
int maxCount = 0;
for (int f : freq) {
if (f == maxFreq) maxCount++;
}
int frame = (maxFreq - 1) * (n + 1) + maxCount;
return max((int)tasks.size(), frame);
}
};class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
freq = [0] * 26
for c in tasks:
freq[ord(c) - ord('A')] += 1
max_freq = max(freq)
max_count = sum(1 for f in freq if f == max_freq)
frame = (max_freq - 1) * (n + 1) + max_count
return max(len(tasks), frame)var leastInterval = function(tasks, n) {
const freq = new Array(26).fill(0);
for (const c of tasks) {
freq[c.charCodeAt(0) - 65]++;
}
let maxFreq = 0;
for (const f of freq) {
if (f > maxFreq) maxFreq = f;
}
let maxCount = 0;
for (const f of freq) {
if (f === maxFreq) maxCount++;
}
const frame = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(tasks.length, frame);
};中文
题目概述
给定一组任务（大写字母）和冷却时间 n，相同任务两次执行之间至少间隔 n 个单位时间。求完成所有任务的最短总时间。
核心思路
决定下界的是出现次数最多的任务。若最大频次为 maxFreq，则会形成 maxFreq - 1 个完整“间隔层”，每层长度为 n + 1。与最大频次并列的任务会占据最后一层尾部。
基线做法与不足
用大根堆按轮次模拟也能做，但每个时间片都涉及堆操作。这个题可以直接计数 + 公式一次算出答案。
最优算法（步骤）
1）统计 26 个字母任务的频次。
2）求 maxFreq 与 maxCount（有多少个任务达到最大频次）。
3）计算框架长度：(maxFreq - 1) * (n + 1) + maxCount。
4）答案为 max(任务总数, 框架长度)。
复杂度分析
时间复杂度：O(m + 26)，其中 m 为任务数。
空间复杂度：O(26)。
常见陷阱
- 忘记与任务总数取最大值，导致空闲位被高估。
- 最大频次并列数量 maxCount 统计错误。
- 公式写成 maxFreq * (n + 1) 等 off-by-one 形式。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;
int maxFreq = 0;
for (int f : freq) maxFreq = Math.max(maxFreq, f);
int maxCount = 0;
for (int f : freq) {
if (f == maxFreq) maxCount++;
}
int frame = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(tasks.length, frame);
}
}func leastInterval(tasks []byte, n int) int {
freq := make([]int, 26)
for _, c := range tasks {
freq[c-'A']++
}
maxFreq := 0
for _, f := range freq {
if f > maxFreq {
maxFreq = f
}
}
maxCount := 0
for _, f := range freq {
if f == maxFreq {
maxCount++
}
}
frame := (maxFreq-1)*(n+1) + maxCount
if len(tasks) > frame {
return len(tasks)
}
return frame
}class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26, 0);
for (char c : tasks) freq[c - 'A']++;
int maxFreq = 0;
for (int f : freq) maxFreq = max(maxFreq, f);
int maxCount = 0;
for (int f : freq) {
if (f == maxFreq) maxCount++;
}
int frame = (maxFreq - 1) * (n + 1) + maxCount;
return max((int)tasks.size(), frame);
}
};class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
freq = [0] * 26
for c in tasks:
freq[ord(c) - ord('A')] += 1
max_freq = max(freq)
max_count = sum(1 for f in freq if f == max_freq)
frame = (max_freq - 1) * (n + 1) + max_count
return max(len(tasks), frame)var leastInterval = function(tasks, n) {
const freq = new Array(26).fill(0);
for (const c of tasks) {
freq[c.charCodeAt(0) - 65]++;
}
let maxFreq = 0;
for (const f of freq) {
if (f > maxFreq) maxFreq = f;
}
let maxCount = 0;
for (const f of freq) {
if (f === maxFreq) maxCount++;
}
const frame = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(tasks.length, frame);
};
Comments