Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

621. Task Scheduler

Time: $O(|\texttt{tasks}|)$

Space: $O(26)$

			


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()));
  }
};




			


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);
  }
}




			


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))