Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Task Scheduler

Task Scheduler

Master this topic with zero to advance depth.

Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks can be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of time that the CPU will take to finish all the given tasks.

Visual Representation

tasks = [A, A, A, B, B, B], n = 2 Simulation Steps: 1. A (freq 3->2) | Waitlist: [(A, T=3)] 2. B (freq 3->2) | Waitlist: [(A, T=3), (B, T=4)] 3. IDLE | Waitlist: [(A, T=3), (B, T=4)] 4. A (freq 2->1) | A returns from waitlist at T=3 ... Result: A B IDLE A B IDLE A B = 8 units
Medium

Examples

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Approach 1

Level I: Max-Heap + Cooling Queue (Simulation)

Intuition

We want to process the most frequent tasks first to minimize idle time. Use a Max-Heap to keep track of task frequencies and a Queue to manage tasks in their cooldown period.

Thought Process

  1. Count frequency of each task.
  2. Push frequencies into a Max-Heap.
  3. While heap or cooldown queue is not empty:
    • Increment time.
    • If heap has tasks, take the most frequent, decrement its count, and if count > 0, add to queue with its 'available time'.
    • If queue has a task whose cooldown is over, push it back to the heap.
⏱ O(N * log 26) = O(N)💾 O(1) (only 26 uppercase letters)

Detailed Dry Run

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

  1. Heap: [A:3, B:3], Queue: [], Time: 0
  2. Time 1: Process A. Heap [B:3], Queue [(A:2, T=4)]
  3. Time 2: Process B. Heap [], Queue [(A:2, T=4), (B:2, T=5)]
  4. Time 3: Idle. Queue is cool until T=4.
  5. Time 4: Q.pop A. Heap [A:2]... and so on until 8.
java
import java.util.*;
class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : tasks) counts.put(c, counts.getOrDefault(c, 0) + 1);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(counts.values());
        Queue<int[]> q = new LinkedList<>();
        int time = 0;
        while (!pq.isEmpty() || !q.isEmpty()) {
            time++;
            if (!pq.isEmpty()) {
                int cnt = pq.poll() - 1;
                if (cnt > 0) q.add(new int[]{cnt, time + n});
            }
            if (!q.isEmpty() && q.peek()[1] == time) pq.add(q.poll()[0]);
        }
        return time;
    }
}
Approach 2

Level II: Greedy (Simplified Priority Queue)

Intuition

Always process the task with the highest remaining frequency. We use a single loop to calculate the size of chunks of size n+1n+1.

Thought Process

  1. Count frequencies.
  2. Use a Priority Queue (Max-Heap).
  3. In each chunk of n+1n+1 time units, pick tasks from heap.
  4. If heap is empty but we still have tasks to process (temporarily removed), add 'idle' counts.
⏱ O(N)💾 O(1)

Detailed Dry Run

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

  1. Frequencies: {A:3, B:3}
  2. Iteration 1: Chunk size 3. Pick A (rem 2), B (rem 2). Total time 2. Remaining tasks exist, so add 1 idle. Time 3.
  3. Iteration 2: Pick A (rem 1), B (rem 1). Time 6.
  4. Iteration 3: Pick A (rem 0), B (rem 0). Time 8. Done.
java
import java.util.*;
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char c : tasks) freqs[c - 'A']++;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int f : freqs) if (f > 0) pq.add(f);
        int time = 0;
        while (!pq.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int cycle = n + 1;
            while (cycle > 0 && !pq.isEmpty()) {
                temp.add(pq.poll());
                time++; cycle--;
            }
            for (int f : temp) if (--f > 0) pq.add(f);
            if (pq.isEmpty()) break;
            time += cycle; // Idle time
        }
        return time;
    }
}
Approach 3

Level III: Greedy (Mathematical)

Intuition

The total time is determined by the task with the maximum frequency. Let the maximum frequency be maxFreq. There are maxFreq - 1 gaps between these tasks, each of size n. We fill these gaps with other tasks. If the total units required is less than the total number of tasks, the answer is the total tasks.

Formula

partCount = maxFreq - 1 partLength = n - (countOfTasksWithMaxFreq - 1) emptySlots = partCount * partLength availableTasks = tasks.length - maxFreq * countOfTasksWithMaxFreq idles = max(0, emptySlots - availableTasks) Result = tasks.length + idles

⏱ O(N)💾 O(1) (26 tasks)

Detailed Dry Run

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

  1. maxFreq = 3 (A and B both have 3).
  2. Max freq task count = 2 (A and B).
  3. Formula: (3-1) * (2+1) + 2 = 8. Total Time = 8.
java
import java.util.Arrays;

public class Main {
    public static int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char c : tasks) freqs[c - 'A']++;
        Arrays.sort(freqs);
        
        int maxFreq = freqs[25];
        int idleTime = (maxFreq - 1) * n;
        
        for (int i = 24; i >= 0 && freqs[i] > 0; i--) {
            idleTime -= Math.min(maxFreq - 1, freqs[i]);
        }
        
        return idleTime > 0 ? tasks.length + idleTime : tasks.length;
    }

    public static void main(String[] args) {
        System.out.println(leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
    }
}
← Previous QuestionKth Largest Element in an Array
Next Question →K Closest Points to Origin