Task Scheduler — Greedy with Most Frequent First
Advertisement
Problem 277 · Task Scheduler
Difficulty: Medium · Pattern: Greedy / Max Frequency
Find minimum CPU intervals needed to execute tasks with cooldown n between same tasks.
Intuition
Math formula: if f = max frequency, and count_max = tasks with that frequency: result = max(len(tasks), (f-1)*(n+1) + count_max)
Solutions
# Python — formula
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
f = max(freq.values())
count_max = sum(1 for v in freq.values() if v == f)
return max(len(tasks), (f-1)*(n+1) + count_max)
// Java
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char t : tasks) freq[t-'A']++;
int f = 0;
for (int x : freq) f = Math.max(f, x);
int countMax = 0;
for (int x : freq) if (x == f) countMax++;
return Math.max(tasks.length, (f-1)*(n+1) + countMax);
}
// C++
int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26,0);
for (char t : tasks) freq[t-'A']++;
int f = *max_element(freq.begin(), freq.end());
int countMax = count(freq.begin(), freq.end(), f);
return max((int)tasks.size(), (f-1)*(n+1)+countMax);
}
Complexity
- Time: O(n)
- Space: O(1) (26 letters)
Advertisement