Task Scheduler

Medium Arrays & Hashing Greedy Original on LeetCode

Task Scheduler is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (count the most frequent task), runs in O(N) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (simulate every time unit) up.

Problem

A machine has to run a list of tasks, each labeled with an uppercase letter. Every task takes exactly one time unit, and the tasks may be run in any order. In each time unit the machine either runs one task or stays idle.

There is a cooling rule: two tasks with the same letter must be separated by at least n time units, so after running a task with label X, the next X can start no earlier than n + 1 units later.

Return the minimum number of time units needed to finish all the tasks.

Examples

Example 1

Input
tasks = ["X", "X", "X", "Y", "Y", "Z"], n = 2
Output
7
Why
One best order is X Y Z X Y idle X: between two X's there are always at least 2 other slots.

Example 2

Input
tasks = ["P", "P", "Q", "Q", "R", "R"], n = 1
Output
6
Why
P Q R P Q R never needs an idle slot, so the time equals the number of tasks.

Example 3

Input
tasks = ["K", "K", "K", "K"], n = 3
Output
13
Why
Only one kind of task exists, so three idle slots must follow each K except the last: K _ _ _ K _ _ _ K _ _ _ K.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (simulate every time unit)O(T · 26)O(1)
Better (max-heap with a cooldown queue)O(N log 26)O(26)
Optimal (count the most frequent task)O(N)O(1)

1Brute force (simulate every time unit)

TimeO(T · 26)T is the total length of the schedule, at most about tasks.length · (n + 1), and each unit scans 26 letters.
SpaceO(1)Two arrays of 26 entries.

Run the clock one unit at a time. Track how many copies of each letter remain and the earliest time each letter may run again. At every unit, among the letters that are allowed now, run the one with the most copies left; if none is allowed, stay idle.

  1. Count each letter; set nextFree[c] = 0 for all letters.
  2. While tasks remain: scan the 26 letters for one with count > 0 and nextFree <= time, preferring the largest count.
  3. If found, decrement its count and set nextFree = time + n + 1. Otherwise idle.
  4. Advance time by 1. Return time when no tasks remain.
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char c : tasks) count[c - 'A']++;
        int[] nextFree = new int[26];
        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) {
                count[pick]--;
                nextFree[pick] = time + n + 1;
                remaining--;
            }
            time++;
        }
        return time;
    }
}

2Better (max-heap with a cooldown queue)

TimeO(N log 26)Each of the N tasks is popped and pushed once, and the heap holds at most 26 letters.
SpaceO(26)The heap and the queue hold at most 26 entries together.

Keep the remaining counts of the available letters in a max-heap and the cooling letters in a queue with the time they become free. At each step move the letters whose cooldown ended back into the heap, then run the most frequent one. When the heap is empty, jump the clock straight to the next release instead of idling one unit at a time.

  1. Push every non-zero letter count into a max-heap.
  2. Loop while the heap or the queue is non-empty: if the heap is empty, set time to the release time at the queue front.
  3. Move every queued letter whose release time <= time into the heap.
  4. Pop the largest count, run it (time++), and if copies remain, queue (count - 1, time + n).
  5. Return time.
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char c : tasks) count[c - 'A']++;
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : count) if (c > 0) heap.add(c);
        Deque<int[]> cooling = new ArrayDeque<>(); // {remaining, releaseTime}
        int time = 0;
        while (!heap.isEmpty() || !cooling.isEmpty()) {
            if (heap.isEmpty()) time = Math.max(time, cooling.peekFirst()[1]);
            while (!cooling.isEmpty() && cooling.peekFirst()[1] <= time) {
                heap.add(cooling.pollFirst()[0]);
            }
            int c = heap.poll() - 1;
            time++;
            if (c > 0) cooling.addLast(new int[] { c, time + n });
        }
        return time;
    }
}

3Optimal (count the most frequent task)

TimeO(N)One pass to count, then a scan over 26 letters.
SpaceO(1)A fixed array of 26 counts.

Let f be the highest count and k the number of letters that reach it. Lay the schedule out in rows of width n + 1, each starting with one copy of a most frequent letter: there are f - 1 full rows plus a last row holding the k letters with count f, giving (f - 1) · (n + 1) + k slots. Other tasks fill the idle spots; if there are more tasks than spots, rows simply get wider and no idle slot is needed, so the answer is the number of tasks.

  1. Count each letter; f = the maximum count.
  2. k = how many letters have count f.
  3. Return max(tasks.length, (f - 1) · (n + 1) + k).
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char c : tasks) count[c - 'A']++;
        int f = 0;
        for (int c : count) f = Math.max(f, c);
        int k = 0;
        for (int c : count) if (c == f) k++;
        return Math.max(tasks.length, (f - 1) * (n + 1) + k);
    }
}

Edge cases to test

  • n = 0: no cooling, the answer is the number of tasks
  • A single task: answer 1
  • Several letters tie for the highest count; they all occupy the last row
  • So many different letters that the gaps fill up completely: the answer is just the number of tasks

Hints

Hint 1

The most frequent task decides the shape. If it appears f times, its copies split the timeline into f - 1 gaps of size n that must be filled by something, other tasks or idle.

Hint 2

Picture f - 1 full rows of width n + 1, plus a final row containing every task that also appears f times.

Hint 3

The answer is max(tasks.length, (f - 1) · (n + 1) + count of letters that appear f times). Extra tasks only make rows wider, never add idles.

FAQ

What is the best time complexity for Task Scheduler?

Optimal (count the most frequent task) runs in O(N) time and O(1) extra space. One pass to count, then a scan over 26 letters.

Which pattern does Task Scheduler use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Task Scheduler?

Yes. Brute force (simulate every time unit) takes O(T · 26) time and O(1) space. Run the clock one unit at a time.

Which edge cases should I test for Task Scheduler?

n = 0: no cooling, the answer is the number of tasks; A single task: answer 1; Several letters tie for the highest count; they all occupy the last row; So many different letters that the gaps fill up completely: the answer is just the number of tasks.