Leetcode

Task Scheduler

  • Time:O(|\texttt{tasks}|)
  • Space:O(26)

C++

class Solution {
 public:
  int leastInterval(vector<char>& tasks, int n) {
    if (n == 0)
      return tasks.size();

    vector<int> count(26);

    for (const char task : tasks)
      ++count[task - 'A'];

    const int maxFreq = *max_element(begin(count), end(count));
    // put the most frequent task in the slot first
    const int maxFreqTaskOccupy = (maxFreq - 1) * (n + 1);
    // get # of tasks with same frequency as maxFreq,
    // we'll append them after maxFreqTaskOccupy
    const int nMaxFreq = std::count(begin(count), end(count), maxFreq);
    // max(
    //   the most frequent task is frequent enough to force some idle slots,
    //   the most frequent task is not frequent enough to force idle slots
    // )
    return max(maxFreqTaskOccupy + nMaxFreq, static_cast<int>(tasks.size()));
  }
};

JAVA

class Solution {
  public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];

    for (final char task : tasks)
      ++count[task - 'A'];

    final int maxFreq = Arrays.stream(count).max().getAsInt();
    // put the most frequent task in the slot first
    final int maxFreqTaskOccupy = (maxFreq - 1) * (n + 1);
    // get # of tasks with same frequency as maxFreq,
    // we'll append them after maxFreqTaskOccupy
    final int nMaxFreq = (int) Arrays.stream(count).filter(c -> c == maxFreq).count();
    // max(
    //   the most frequent task is frequent enough to force some idle slots,
    //   the most frequent task is not frequent enough to force idle slots
    // )
    return Math.max(maxFreqTaskOccupy + nMaxFreq, tasks.length);
  }
}

Python

class Solution:
  def leastInterval(self, tasks: List[str], n: int) -> int:
    count = Counter(tasks)
    maxFreq = max(count.values())
    # put the most frequent task in the slot first
    maxFreqTaskOccupy = (maxFreq - 1) * (n + 1)
    # get # of tasks with same frequency as maxFreq,
    # we'll append them after maxFreqTaskOccupy
    nMaxFreq = sum(value == maxFreq for value in count.values())
    # max(
    #   the most frequent task is frequent enough to force some idle slots,
    #   the most frequent task is not frequent enough to force idle slots
    # )
    return max(maxFreqTaskOccupy + nMaxFreq, len(tasks))