Crack the Backend

Problem Statement

You are given a character array tasks (each is 'A' to 'Z') and an integer n (cooldown). The same task cannot run within n slots of each other (there must be at least n slots between two runs of the same task). You can do one task per slot or idle. Return the minimum number of slots needed to complete all tasks.

Key Observations

Max-heap by frequency: Count task frequencies. In each "round" we can run up to n+1 distinct tasks (or idle). Always schedule the most frequent first. Use a max-heap of (remaining count, task). Each round: poll up to n+1 tasks, decrement count, push back if count > 0. Total slots = sum of round sizes (last round may have fewer than n+1). A closed form exists: if max freq is M and there are t tasks with freq M, answer = max(len(tasks), (M-1)*(n+1) + t).

Approach

High-level: Count freq; max-heap (freq, task). While heap not empty: poll up to n+1, decrement and push back; add (n+1 or remaining) to total. Return total.

Steps: int[] freq; for (c : tasks) freq[c-'A']++; PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a); for (int f : freq) if (f>0) pq.offer(f); int time = 0; while (!pq.isEmpty()) { int k = 0; List<Integer> next = new ArrayList<>(); for (int i = 0; i <= n && !pq.isEmpty(); i++) { int f = pq.poll()-1; if (f>0) next.add(f); k++; } for (int f : next) pq.offer(f); time += pq.isEmpty() && next.isEmpty() ? k : n+1; } return time;

Implementation

Java

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];

    for (char c : tasks) {
        freq[c-'A']++;
    }

    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a);

    for (int f : freq) {
        if (f > 0) {
            pq.offer(f);
        }
    }

    int time = 0;

    while (!pq.isEmpty()) {
        int cycle = n + 1;
        List<Integer> next = new ArrayList<>();

        while (cycle > 0 && !pq.isEmpty()) {
            int f = pq.poll() - 1;

            if (f > 0) {
                next.add(f);
            }

            time++;
            cycle--;
        }

        for (int f : next) {
            pq.offer(f);
        }

        if (!pq.isEmpty()) {
            time += cycle;
        }
    }

    return time;
}

Test Cases

Example 1

Input

tasks = ["A","A","A","B","B","B"], n = 2

Expected

8

Explanation

A->B->idle->A->B->idle->A->B.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.