Back to DSA

Task Scheduler

medium
Acceptance: 44%
HeapGreedyArray

A CPU must execute a set of tasks represented by characters. Between two executions of the same task there must be at least n intervals of cooldown (other tasks or idle slots). Determine the minimum total number of intervals the CPU needs to complete every task.

Examples

Example 1:
Input:tasks = ['X','X','X','Y','Y','Y'], n = 2
Output:8
Example 2:
Input:tasks = ['X','X','X','Y','Y','Y'], n = 0
Output:6

Hints

Related Problems

Daily TemperaturesmediumAsteroid CollisionmediumLargest Rectangle in HistogramhardTrapping Rain WaterhardTop K Frequent Elementsmedium
00:00
import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char t : tasks) freq[t - 'A']++;
        Arrays.sort(freq);
        int maxFreq = freq[25];
        int idleSlots = (maxFreq - 1) * n;
        for (int i = 24; i >= 0 && freq[i] > 0; i--) {
            idleSlots -= Math.min(freq[i], maxFreq - 1);
        }
        return tasks.length + Math.max(0, idleSlots);
    }
}
Time complexityO(n)
Space complexityO(1)