621. Task Scheduler LeetCode Solution

In this guide, you will get 621. Task Scheduler LeetCode Solution with the best time and space complexity. The solution to Task Scheduler problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Task Scheduler solution in C++
Task Scheduler solution in Java
Task Scheduler solution in Python
Additional Resources

621. Task Scheduler LeetCode Solution image

Problem Statement of Task Scheduler

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there’s a constraint: there has to be a gap of at least n intervals between two tasks with the same label.
Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = [“A”,”C”,”A”,”B”,”D”,”B”], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.
With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = [“A”,”A”,”A”, “B”,”B”,”B”], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.
There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

1 <= tasks.length <= 104
tasks[i] is an uppercase English letter.
0 <= n <= 100

Complexity Analysis

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

621. Task Scheduler LeetCode Solution in 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 = ranges::max(count);
    // Put the most frequent task in the slot first.
    const int maxFreqTaskOccupy = (maxFreq - 1) * (n + 1);
    // Get the number of tasks with the same frequency as `maxFreq`, we'll
    // append them after `maxFreqTaskOccupy`.
    const int nMaxFreq = ranges::count(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()));
  }
};
/* code provided by PROGIEZ */

621. Task Scheduler LeetCode Solution in 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 the number of tasks with the 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);
  }
}
// code provided by PROGIEZ

621. Task Scheduler LeetCode Solution in Python

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 the number of tasks with same frequency as maxFreq, we'll append them after the
    # `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))
 # code by PROGIEZ