☕ DSA Java Articles

Topics › Heaps › Medium Problems

Task Scheduler

Medium TUF ID 1008 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A CPU has to run a list of tasks. Each task is an uppercase letter and takes exactly one time slot. In every slot the CPU either runs one task or sits idle. Tasks may run in any order, but two runs of the same letter must have at least n slots between them. Return the minimum number of slots needed to finish every task, idle slots included.

Constraints: 1 ≤ tasks.length ≤ 10^4, every task is a letter 'A' to 'Z', 0 ≤ n ≤ 100.

Example 1

tasks = [A, A, A, B, B, B], n = 2
answer = 8               // A B idle A B idle A B

Example 2

tasks = [A, C, A, B, D, B], n = 1
answer = 6               // A B A B C D: enough variety that no slot is wasted

Example 3

tasks = [A, A, A, B, B, B], n = 3
answer = 10              // A B _ _ A B _ _ A B

Only the count of each letter matters, not where it sits in the input. All three approaches start by counting letters into an array of 26.

Approach 1: Brute force, slot-by-slot simulation

Intuition. Pretend to be the CPU. In each slot, look at the letters that still have copies left and whose cooldown has expired, and run one of them. If no letter is allowed, the slot is idle.

The only real decision is which allowed letter to run, and the answer is: the one with the most copies left. The letter with the most copies is the one that forces idle time, because its copies must be spread n + 1 apart. Running it as early as possible starts that chain early; postponing it only pushes the whole chain later. Picking any allowed letter can fail. With tasks = [A, B, C, C, C] and n = 2, running letters alphabetically gives A B C _ _ C _ _ C (9 slots), while running the most frequent first gives C A B C _ _ C (7 slots).

Algorithm.

  1. Count each letter. Keep nextFree[c], the earliest slot in which letter c may run again (initially 0).
  2. While tasks remain, for the current slot time:
    • Among letters with count[c] > 0 and nextFree[c] <= time, pick the one with the largest count.
    • If one exists, decrement its count, set its nextFree to time + n + 1, and decrement remaining.
    • Advance time by one (an idle slot also costs a unit).
  3. Return time.
static int bruteForce(char[] tasks, int n) {
    int[] count = new int[26];
    for (char t : tasks) count[t - 'A']++;
    int[] nextFree = new int[26];            // earliest slot in which each letter may run again
    int remaining = tasks.length, time = 0;
    while (remaining > 0) {
        int pick = -1;
        for (int c = 0; c < 26; c++) {
            if (count[c] > 0 && nextFree[c] <= time && (pick == -1 || count[c] > count[pick])) pick = c;
        }
        if (pick != -1) {                    // otherwise this slot is idle
            count[pick]--;
            nextFree[pick] = time + n + 1;
            remaining--;
        }
        time++;
    }
    return time;
}

Complexity. Time O(26 · answer): every slot, idle or not, scans the 26 letters, and the answer is at most about tasks.length · (n + 1). Space O(1): two arrays of 26.

With 10^4 tasks of one letter and n = 100 the answer is about 10^6 slots, so this is still fast in practice. Its weakness is that it walks through every idle slot one at a time and rescans all letters each time.

Approach 2: Better, max-heap plus cooldown queue

Intuition. The simulation keeps asking two questions: “which runnable letter has the most copies?” and “which letters have just finished cooling down?” A max-heap of remaining counts answers the first in O(log 26). A FIFO queue answers the second: when a letter runs in slot t, it becomes runnable again at slot t + n + 1. Slots only move forward, so letters enter the queue in increasing order of that ready time. The front of the queue is always the next letter to wake up.

The queue also lets us skip idle stretches. If the heap is empty, nothing can run until the front of the queue wakes up, so we jump time straight to its ready slot. The jumped-over slots are the idle slots, and they are still counted because time moved past them.

The heap stores only counts, not letters. Which letter it is does not matter, only how many copies remain.

Algorithm.

  1. Count letters and push every non-zero count into a max-heap ready.
  2. Keep a deque cooling of pairs {remainingCount, readySlot}.
  3. While either structure is non-empty:
    • If ready is empty, set time to the ready slot at the front of cooling.
    • Move every cooling entry whose ready slot is <= time into ready.
    • Pop the largest count, run it (count minus one), and if copies remain, append {left, time + n + 1} to cooling.
    • Advance time.
  4. Return time.
static int better(char[] tasks, int n) {
    int[] count = new int[26];
    for (char t : tasks) count[t - 'A']++;
    PriorityQueue<Integer> ready = new PriorityQueue<>(Collections.reverseOrder());   // remaining counts
    for (int c : count) if (c > 0) ready.add(c);
    Deque<int[]> cooling = new ArrayDeque<>();   // {remainingCount, slotWhenReadyAgain}, ordered by slot
    int time = 0;
    while (!ready.isEmpty() || !cooling.isEmpty()) {
        if (ready.isEmpty()) time = Math.max(time, cooling.peekFirst()[1]);   // skip the idle stretch
        while (!cooling.isEmpty() && cooling.peekFirst()[1] <= time) ready.add(cooling.pollFirst()[0]);
        int left = ready.poll() - 1;
        if (left > 0) cooling.addLast(new int[]{left, time + n + 1});
        time++;
    }
    return time;
}

Complexity. Time O(T log 26), which is O(T) for T tasks. Thanks to the jump, every iteration runs exactly one task, and each heap operation works on at most 26 entries. Space O(26).

This is the approach to reach for when the problem changes shape, for example when tasks have different durations or when you must output the actual schedule. Simulation with a heap adapts easily; the closed formula below does not.

Approach 3: Optimal, counting frames

Intuition. Look at the most frequent letter, say A with maxFreq copies. Its copies must be at least n + 1 slots apart, so the schedule contains at least this skeleton:

A ? ? | A ? ? | A ? ? | ... | A

There are maxFreq - 1 full frames of length n + 1, each starting with an A, followed by the final A. That alone needs (maxFreq - 1) · (n + 1) + 1 slots.

If several letters tie for the maximum, say maxCount of them, each one also has a copy left over after the last full frame, so the final partial frame holds maxCount letters instead of one:

lowerBound = (maxFreq - 1) · (n + 1) + maxCount

Every other letter has fewer than maxFreq copies, so its copies can go into different frames, one copy per frame. Copies in different frames are at least n + 1 slots apart, so they never break the cooldown. Unused ? slots become idle.

There is one more case. If there are so many other tasks that the ? slots overflow, we simply make frames longer than n + 1. Longer frames only increase the distance between equal letters, so nothing breaks, and now there are no idle slots at all: the answer is just tasks.length. Combining both cases:

answer = max(tasks.length, (maxFreq - 1) · (n + 1) + maxCount)

Neither part can be beaten: every task needs its own slot, and the skeleton of the most frequent letters is forced.

Algorithm.

  1. If there are no tasks, return 0.
  2. Count letters, find maxFreq, and count how many letters reach it (maxCount).
  3. Return max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount).
static int optimal(char[] tasks, int n) {
    if (tasks.length == 0) return 0;
    int[] count = new int[26];
    for (char t : tasks) count[t - 'A']++;
    int maxFreq = 0;
    for (int c : count) maxFreq = Math.max(maxFreq, c);
    int maxCount = 0;                        // how many letters reach maxFreq
    for (int c : count) if (c == maxFreq) maxCount++;
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
}

Dry run on example 1, [A, A, A, B, B, B], n = 2:

quantity value
counts A = 3, B = 3
maxFreq 3
maxCount 2 (A and B)
full frames (3 - 1) · (2 + 1) = 6 slots: A B _ twice
final frame A B, 2 slots
answer max(6, 6 + 2) = 8

And on [A×6, B, C, D, E, F, G] with n = 2: maxFreq = 6, maxCount = 1, so the bound is 5 · 3 + 1 = 16, larger than the 12 tasks. The six fillers occupy 6 of the 10 gaps and 4 slots stay idle.

Complexity. Time O(T) to count, plus constant work over 26 letters. Space O(1).

Edge cases and pitfalls