Task Scheduler

Intuitionwhy the most frequent task controls the schedule

Take the task that appears most often, with frequency maxFreq. Between two consecutive copies of this task, at least n other intervals must pass, so the first maxFreq - 1 copies force maxFreq - 1 frames of length n + 1: one interval for the task itself and n intervals after it. The final copy does not need a cooling interval after it.

If several task labels share the maximum frequency, their copies can occupy the ends of the forced frames. With maxFreq copies and countMax tied labels, the final frame ends with countMax tasks, so the forced length is (maxFreq - 1) x (n + 1) + countMax. Every other task can fill an idle position inside those frames. If there are more other tasks than gaps, no idle time is needed and the answer is simply the number of tasks.

Approach

1. 1Count the frequency of each uppercase letter in an array of 26 entries, because only the number of copies of each label affects the minimum schedule length.
2. 2Scan the frequencies while tracking maxFreq and countMax, resetting countMax when a larger frequency appears and incrementing it on a tie; both values are needed to describe the forced frames correctly.
3. 3Compute partCount as maxFreq - 1, because only the gaps before the final copy require cooling, and compute partLength as n + 1, because each such frame contains one maximum task plus n separating intervals.
4. 4Set total to partCount x partLength + countMax, because the first maxFreq - 1 frames are full and the final frame contains one task for each label tied at maxFreq.
5. 5Return the larger of tasks.size() and total, because the frame arrangement is a lower bound, while a schedule cannot finish in fewer intervals than the number of actual tasks; extra tasks may fill all the gaps and make the lower bound smaller than the task count.

Complexity

Annotated solutionC++ · formula · constant extra space

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    int leastInterval(string tasks, int n) {
        int freq[26] = {0};
        for (char c : tasks) {
            freq[c - 'A']++;
        }

        int maxFreq = 0;
        int countMax = 0;
        for (int f : freq) {
            if (f > maxFreq) {
                maxFreq = f;
                countMax = 1;
            } else if (f == maxFreq) {
                countMax++;
            }
        }

        int partCount = maxFreq - 1;
        int partLength = n + 1;
        int forcedLength = partCount * partLength + countMax;

        return max(static_cast<int>(tasks.size()), forcedLength);
    }
};

The important placement is the final max call. The frame calculation counts every forced position around the most frequent tasks, but it does not promise that all remaining tasks fit inside those positions. When the remaining tasks are abundant, they occupy the gaps and extend the schedule beyond the frame lower bound; taking the maximum handles both the idle and no-idle cases.

The heap alternativea direct simulation when you want the schedule itself

A max heap gives the most frequent currently available task priority. Process time in cycles of n + 1 intervals: remove up to n + 1 different tasks from the heap, decrease their frequencies, and return unfinished tasks only after the cycle ends. Returning them later enforces the cooldown. This is a different arrangement, not an optimisation: it uses O(tasks.length) heap and cycle storage instead of the formula's O(1) extra space.

#include <algorithm>
#include <queue>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int leastInterval(string tasks, int n) {
        int freq[26] = {0};
        for (char c : tasks) {
            freq[c - 'A']++;
        }

        priority_queue<int> available;
        for (int f : freq) {
            if (f > 0) {
                available.push(f);
            }
        }

        int elapsed = 0;
        int cycleLength = n + 1;

        while (!available.empty()) {
            vector<int> used;
            int cycleUsed = 0;

            while (cycleUsed < cycleLength && !available.empty()) {
                int remaining = available.top();
                available.pop();
                if (--remaining > 0) {
                    used.push_back(remaining);
                }
                cycleUsed++;
            }

            elapsed += cycleUsed;
            if (!available.empty()) {
                elapsed += cycleLength - cycleUsed;
            }

            for (int remaining : used) {
                available.push(remaining);
            }
        }

        return elapsed;
    }
};

Common mistakestwo wrong formula shapes that look plausible