Task Scheduler

Problem

Given an array of CPU tasks (each labelled A-Z) and an integer n, the same task must be separated by at least n idle cycles. Return the minimum number of cycles to finish all tasks.

Constraints

• 1 ≤ tasks.length ≤ 10⁴
• 0 ≤ n ≤ 100

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def leastInterval(self, tasks, n):
        from collections import Counter
        counts = Counter(tasks)
        mx = max(counts.values())
        mx_count = sum(1 for v in counts.values() if v == mx)
        return max(len(tasks), (mx - 1) * (n + 1) + mx_count)

Java

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char task : tasks) count[task - 'A']++;

        // Max-heap of remaining counts: always run the most-loaded task
        // that is allowed to run, then park it in a cooldown queue for
        // n ticks. An empty heap with a non-empty queue is an idle tick.
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : count) if (c > 0) heap.offer(c);

        Deque<int[]> cooldown = new ArrayDeque<>(); // { remaining, readyAt }
        int time = 0;
        while (!heap.isEmpty() || !cooldown.isEmpty()) {
            time++;
            if (!heap.isEmpty()) {
                int left = heap.poll() - 1;
                if (left > 0) cooldown.offer(new int[]{ left, time + n });
            }                                       // else: idle tick
            if (!cooldown.isEmpty() && cooldown.peek()[1] == time)
                heap.offer(cooldown.poll()[0]);
        }
        return time;

        // O(1) math alternative: (maxFreq - 1) * (n + 1) + (#tasks tied
        // at maxFreq), floored at tasks.length.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.