Problem Description

The Task Scheduler problem asks you to determine the minimum number of units of time that the CPU will take to finish all given tasks. Each task is represented by a capital letter (from 'A' to 'Z'), and each task takes exactly one unit of time to complete. However, the same task must be separated by at least n units of time (the "cooldown period") before it can be executed again. During the cooldown period, the CPU can either execute a different task or be idle.

• You are given an array tasks of characters representing the tasks to perform.
• You are also given a non-negative integer n representing the cooldown period between two same tasks.
• Your goal is to find the least number of time units the CPU will take to finish all the given tasks, following the cooldown constraint.

Constraints:

• Each task can be used only as many times as it appears in the input.
• There is always at least one valid way to schedule the tasks.
• Tasks can be executed in any order.

Thought Process

At first glance, it may seem that we need to simulate the entire scheduling process, placing tasks and idle slots as we go. This brute-force approach would involve at each step choosing the next available task that doesn't violate the cooldown constraint, and inserting idle slots when needed. However, this can be inefficient, especially with long task lists and larger cooldowns.

Upon closer inspection, we notice that the bottleneck is the task with the highest frequency. Since the same task must be separated by at least n units, the most frequent task determines the minimal schedule length. The key insight is that instead of simulating every step, we can use a mathematical formula to compute the minimum time required based on the maximum task frequency and the cooldown.

The challenge is to fit all the other tasks and idle slots around the most frequent tasks as efficiently as possible. If there are enough different tasks to fill the cooldown slots, we can avoid idles altogether.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Count the frequency of each task:
   • We use a hash map or array to count how many times each task appears. This helps us identify the most frequent task(s).
2. Identify the maximum frequency (max_freq):
   • The task(s) with the highest count will dictate the schedule's structure.
3. Count how many tasks have this maximum frequency (max_count):
   • It's possible that more than one task appears with the same highest frequency.
4. Calculate the minimum intervals needed:
   • Think of the schedule as a series of "slots" for the most frequent tasks, with n cooldown slots between them.
   • The formula is: (max_freq - 1) * (n + 1) + max_count.
   • This accounts for all intervals except the last occurrence of the most frequent tasks, which don't need trailing cooldowns.
5. Return the maximum of the computed intervals and the total number of tasks:
   • If there are enough tasks to fill all slots, the answer is just the number of tasks; otherwise, idle slots are needed, and the formula gives the minimal time.

Why use a hash map or array? Because we need to count task frequencies efficiently, and lookups in a hash map or array are O(1).

Example Walkthrough

Example Input: tasks = ['A', 'A', 'A', 'B', 'B', 'B'], n = 2

1. Count frequencies: 'A': 3, 'B': 3
2. max_freq = 3 (both 'A' and 'B'), max_count = 2 (since both have the same frequency)
3. Calculate intervals: (3 - 1) * (2 + 1) + 2 = 2 * 3 + 2 = 6 + 2 = 8
4. Total tasks: 6
5. Answer: max(8, 6) = 8

Schedule could look like: A B idle A B idle A B (or any valid permutation). There are 8 time units in total.

Time and Space Complexity

• Brute-force approach:
  • Would involve simulating each time unit, possibly leading to O(N * n) time, where N is the number of tasks. This is inefficient for large inputs.
• Optimized approach:
  • Counting frequencies: O(N), where N is the number of tasks.
  • Finding max frequency and count: O(1) (since there are at most 26 uppercase letters).
  • Overall time complexity: O(N).
  • Space complexity: O(1) (since the frequency map/array is of fixed size 26).

Summary

The Task Scheduler problem can be solved efficiently by focusing on the task(s) with the highest frequency. By mathematically arranging these tasks with the required cooldowns, and filling in with other tasks as needed, we avoid unnecessary idle time. The elegant formula ensures we only use idle slots when absolutely necessary, and we can compute the answer in linear time with constant space. This approach leverages counting and simple arithmetic rather than brute-force simulation, making it both efficient and easy to understand.

Code Implementation

from collections import Counter

class Solution:
    def leastInterval(self, tasks, n):
        freq = Counter(tasks)
        max_freq = max(freq.values())
        max_count = sum(1 for v in freq.values() if v == max_freq)
        intervals = (max_freq - 1) * (n + 1) + max_count
        return max(len(tasks), intervals)
      

#include <vector>
#include <algorithm>

class Solution {
public:
    int leastInterval(std::vector<char>& tasks, int n) {
        int freq[26] = {0};
        for (char t : tasks) freq[t - 'A']++;
        int max_freq = *std::max_element(freq, freq + 26);
        int max_count = 0;
        for (int i = 0; i < 26; ++i)
            if (freq[i] == max_freq) max_count++;
        int intervals = (max_freq - 1) * (n + 1) + max_count;
        return std::max((int)tasks.size(), intervals);
    }
};
      

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char t : tasks) freq[t - 'A']++;
        int maxFreq = 0, maxCount = 0;
        for (int f : freq) maxFreq = Math.max(maxFreq, f);
        for (int f : freq) if (f == maxFreq) maxCount++;
        int intervals = (maxFreq - 1) * (n + 1) + maxCount;
        return Math.max(tasks.length, intervals);
    }
}
      

var leastInterval = function(tasks, n) {
    let freq = Array(26).fill(0);
    for (let t of tasks) freq[t.charCodeAt(0) - 65]++;
    let maxFreq = Math.max(...freq);
    let maxCount = freq.filter(f => f === maxFreq).length;
    let intervals = (maxFreq - 1) * (n + 1) + maxCount;
    return Math.max(tasks.length, intervals);
};