Task Scheduler

How it works

The task with the highest frequency determines the minimum needed structure of the schedule. If a task appears maxf times, these copies must be at least n units apart. This creates (maxf - 1) "gaps", and each gap must have a length of (n + 1) slots (the task itself + n cooldowns).

If multiple tasks share this maximum frequency (maxCount tasks), they all occupy the final row of the structure.

So the minimal time required to schedule all tasks without violating cooldown rules is: time = (maxf - 1) * (n + 1) + maxCount

However, if the number of tasks is larger than this calculated time, then simply performing all tasks takes longer. Thus, the actual answer must be: max(len(tasks), time)

Steps

1. Count how many times each task appears.
2. Find maxf = the highest task frequency.
3. Count how many tasks have this highest frequency → maxCount.
4. Compute: time = (maxf - 1) * (n + 1) + maxCount
5. Return: max(len(tasks), time)

Complexity

• Time complexity: O(m)
• Space complexity: O(1) since we have at most 26 different characters.

Where m is the number of tasks.

Things to watch for

Not Prioritizing the Most Frequent Task

A greedy approach must always pick the task with the highest remaining count that is not in cooldown. Picking tasks arbitrarily or in the order they appear leads to suboptimal schedules with more idle time than necessary.

Incorrect Cooldown Tracking

When using a heap with a cooldown queue, the task should become available at time current_time + n, not current_time + n + 1. Off-by-one errors in cooldown calculations are common and result in either too many idle slots or cooldown violations.

Forgetting to Count Tasks with Maximum Frequency

In the math-based solution, you must count how many tasks share the maximum frequency (maxCount). Using just 1 instead of maxCount in the formula (maxf - 1) * (n + 1) + maxCount underestimates the required time when multiple tasks have the same highest frequency.

from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = [0] * 26
        for task in tasks:
            count[ord(task) - ord('A')] += 1

        maxf = max(count)
        maxCount = 0
        for i in count:
            maxCount += 1 if i == maxf else 0

        time = (maxf - 1) * (n + 1) + maxCount
        return max(len(tasks), time)

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> count(26, 0);
        for (char task : tasks) {
            count[task - 'A']++;
        }

        int maxf = *max_element(count.begin(), count.end());
        int maxCount = 0;
        for (int i : count) {
            if (i == maxf) {
                maxCount++;
            }
        }

        int time = (maxf - 1) * (n + 1) + maxCount;
        return max((int)tasks.size(), time);
    }
};