Crack the Backend

Problem Statement

You are given an array of CPU tasks (each labeled 'A' to 'Z') and an integer n (cooldown). The same task cannot run in two consecutive slots; there must be at least n slots (or n other tasks) between two runs of the same task. Return the minimum number of slots needed to run all tasks. Idle slots are allowed.

Key Observations

Greedy / formula: The bottleneck is the most frequent task. Suppose the max frequency is maxFreq and countMax tasks have that frequency. We need at least (maxFreq - 1) * (n + 1) + countMax slots to schedule the most frequent tasks with cooldown. If the total number of tasks is larger (many distinct tasks), we can fill without extra idles: so the answer is max((maxFreq-1)*(n+1) + countMax, tasks.length).

Approach

High-level: Count frequency of each task. Find maxFreq and how many tasks have maxFreq. result = (maxFreq-1)*(n+1) + countMax; return max(result, tasks.length).

Steps: int[] freq; for each task freq[c-'A']++. Find max and count of max. Return max((maxFreq-1)*(n+1) + countMax, tasks.length).

Implementation

Java

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

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

    int max = 0, count = 0;

    for (int f : freq) { if (f > max) { max = f; count = 1; }
        else if (f == max) {
        count++; }
    }

    return Math.max(tasks.length, (max-1)*(n+1) + count);
}

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) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.