Skip to content

621. Task Scheduler 👍

  • Time: $O(|\texttt{tasks}|)$
  • Space: $O(26)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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(count.begin(), count.end());
    // 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(count.begin(), count.end(), 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()));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def leastInterval(self, tasks: List[str], n: int) -> int:
    count = collections.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))