Task Scheduler

NeetCode: Task Scheduler · LeetCode: 621. Task Scheduler · Difficulty: Medium

Given an array of tasks (uppercase letters) and a cooldown n, each task takes one unit of time, and two identical tasks must be separated by at least n units. The CPU may idle. Return the minimum total time.

Example

Text

Input:  tasks = ["A","A","A","B","B","B"], n = 2    Output: 8    (A B _ A B _ A B)
Input:  tasks = ["A","A","A","B","B","B"], n = 0    Output: 6

Brute force: simulate time with a heap

At each time step, run the task type with the most remaining copies (a max-heap of counts). After running, a task with copies left goes into a cooldown queue with the time it becomes available again. Tick time until both the heap and the queue are empty.

PriorityQueue is a min-heap, so Collections.reverseOrder() makes the largest count come out first. The cooldown queue is an ArrayDeque. Because the clock moves one unit per step, the ready times in the queue are already in increasing order, so only the front needs checking.

Java

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char t : tasks) {
            counts[t - 'A']++;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : counts) {
            if (c > 0) {
                heap.add(c);
            }
        }
        ArrayDeque<int[]> cooling = new ArrayDeque<>(); // {remaining, ready at time}
        int time = 0;
        while (!heap.isEmpty() || !cooling.isEmpty()) {
            time++;
            if (!heap.isEmpty()) {
                int count = heap.poll();
                if (count > 1) {
                    cooling.addLast(new int[] {count - 1, time + n});
                }
            }
            if (!cooling.isEmpty() && cooling.peekFirst()[1] == time) {
                heap.add(cooling.pollFirst()[0]);
            }
        }
        return time;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
        System.out.println(solution.leastInterval(tasks, 2));
        System.out.println(solution.leastInterval(tasks, 0));
    }
}

Output

8
6

Time: O(T log 26), where T is the answer (including idle time). Space: O(1), since there are at most 26 task types.

Optimal: a formula

The most frequent task decides the shape of the schedule. If it appears max times, it needs max - 1 full gaps of n + 1 slots, followed by one last row that holds every task tied for the maximum count. So the minimum is (max - 1) * (n + 1) + tied. If there are so many different tasks that no idle time is needed, the answer is the number of tasks, so the result is the larger of the two.

The formula uses int. (max - 1) * (n + 1) wraps silently on overflow, so a huge task count or cooldown would need long.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
        System.out.println(solution.leastInterval(tasks, 2));
        System.out.println(solution.leastInterval(tasks, 0));
        System.out.println(solution.leastInterval(new char[] {'A', 'B', 'C', 'D'}, 3));
    }
}

Output

8
6
4

Time: O(m) where m is the number of tasks. Space: O(1).