Sweaty Imposter

Task Scheduler

MediumGreedyNeetCode 150MidOpen on LeetCodeUpdated

You're given a list of tasks, each an uppercase letter, and a cooldown n. A CPU finishes one task or stays idle in each time unit, and two tasks with the same letter must be at least n units apart. Tasks can run in any order. Return the fewest time units needed to finish every task.

Examples

tasks = ["X","X","X","Y","Y"], n = 2 returns 7

X must wait two units between runs, so X, Y, idle, X, Y, idle, X is as short as it gets. The three Xs set the length.

tasks = ["A","B","C","A","B","C"], n = 1 returns 6

A, B, C, A, B, C never repeats a letter back to back, so no idle time is needed.

tasks = ["Q","Q","Q","Q"], n = 0 returns 4

With no cooldown, the four tasks run back to back.

Constraints

  • 1 <= tasks.length <= 10^4
  • tasks[i] is an uppercase English letter.
  • 0 <= n <= 100

Hints

Hint 1

Focus on the task that appears most often. How much idle time does it force on its own?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

The most frequent task sets the shape. If it appears maxCount times, its runs split the timeline into maxCount - 1 frames of length n + 1, followed by a final frame holding every task that ties for the top count, numMax of them. That gives (maxCount - 1) * (n + 1) + numMax units, with the other tasks filling idle slots. If there are more tasks than slots, no idling is needed and the answer is simply tasks.length. Return the larger of the two. Counting is O(t) for t tasks, with O(1) space for 26 letters.

Time

O(t)

Space

O(1)

Pitfall

Forgetting the max with tasks.length. When many distinct tasks fill every frame, the formula undercounts, as in the second example where it gives 5 for 6 tasks.

Solutions

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) count[t - 'A']++;
        int maxCount = 0, numMax = 0;
        for (int c : count) {
            if (c > maxCount) {
                maxCount = c;
                numMax = 1;
            } else if (c == maxCount) {
                numMax++;
            }
        }
        return Math.max(tasks.length, (maxCount - 1) * (n + 1) + numMax);
    }
}
Drill This