Task Scheduler — Greedy with Most Frequent First

Sanjeev SharmaSanjeev Sharma
1 min read

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

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro