Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could 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, there must be at least n units of time between any two same tasks.

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

Additional information

• 1 <= task.length <= 10^4
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100].

Example 1:

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

Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A", "C", "A", "B", "D", "B"], n = 1

Output: 6

Explanation: In this case, any permutation of size 6 would work since n = 1.
["A", "B", "C", "D", "A", "B"] is a valid schedule.

Example 3:

Input: tasks = ["A", "A", "A", "B", "B", "B"], n = 0

Output: 6

Explanation: Since n = 0, no cooldown is required. We can just execute them sequentially.

Simulation (Max-Heap + Queue)

Intuition

The most intuitive way to schedule these tasks is to always prioritize the task that has the highest remaining frequency. If we have 5 'A's and 2 'B's, we really need to get those 'A's out of the way before the cooldowns bottleneck us.

We can simulate the CPU clock ticking unit by unit.

1. We use a Max-Heap to constantly keep track of which available task has the highest count.
2. We use a Queue to act as our "cooldown waiting room". When a task is executed, if it still has remaining instances, we throw it into the queue along with the exact time it will be allowed to exit cooldown.

Algorithm

1. Count the frequencies of each task using a hash map (Counter).
2. Push all the frequencies into a max-heap (by pushing negative values).
3. Initialize a queue and a time variable set to 0.
4. Loop while either the heap or the queue has items:

• Increment time by 1.
• If the heap is not empty, pop the largest frequency. Add 1 to it (which means we did one task, driving the negative number closer to 0).
• If the remaining count is not 0 (meaning it's < 0), append a tuple [remaining_count, time + n] to the queue.
• Check the front of the queue. If the front item's unlock time equals the current time, pop it from the queue and push its count back into the heap.

5. Return the final time.

def least_interval(tasks: list[str], n: int) -> int:
    # Count frequencies
    counts = Counter(tasks)
    
    # Python only has min-heap, so we use negative counts
    max_heap = [-cnt for cnt in counts.values()]
    heapq.heapify(max_heap)
    
    time = 0
    # Queue will store pairs of [remaining_count, idle_time_ends]
    queue = deque()
    
    while max_heap or queue:
        time += 1
        
        if max_heap:
            # Execute the most frequent available task
            remaining_count = heapq.heappop(max_heap) + 1
            if remaining_count != 0:
                # Add to queue to wait out the cooldown 'n'
                queue.append([remaining_count, time + n])
                
        # If the task at the front of the queue is done cooling down, put it back in the heap
        if queue and queue[0][1] == time:
            heapq.heappush(max_heap, queue.popleft()[0])
            
    return time

Time & Space Complexity

• Time complexity: O(N)

• Reason: Counting tasks takes O(N) time. The heap contains at most 26 elements (since there are only 26 uppercase English letters). Thus, heap operations take O(log 26) which simplifies to O(1). We process each task completely, making the overall time complexity linearly dependent on the number of tasks, O(N).

• Space complexity: O(1)

• Reason: The dictionary, heap, and queue will store at most 26 elements (the English alphabet). Therefore, space complexity is strictly bounded by a constant, O(1).

Greedy Math - Optimal

Intuition

If we look closely at the bottleneck, the total time is completely dictated by the task with the highest frequency.

Let's say 'A' appears 3 times and n = 2. We must schedule it like this: A . . A . . A.
Notice the blocks created: we have (3 - 1) = 2 blocks of size (n + 1) = 3.
The final 'A' is just tacked on at the end.

If there are multiple tasks with the same maximum frequency (say 'A' and 'B' both appear 3 times), they just share those blocks and the final piece: A B . A B . A B.

We can calculate the required time mathematically: (max_frequency - 1) * (n + 1) + number_of_max_frequency_tasks.
If we have a lot of other tasks, they will simply fill in the idle slots . without adding any extra time. If we have so many tasks that they spill out of the blocks, the CPU never sits idle, so the answer is just the length of the tasks array itself!

Algorithm

1. Count the frequencies of each task.
2. Find the highest frequency max_freq.
3. Count how many tasks share this exact max_freq.
4. Calculate the mathematically required time: (max_freq - 1) * (n + 1) + count_of_max_freq_tasks.
5. The answer is the maximum between the calculated time and the physical length of the tasks array.

def least_interval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    
    # Find the maximum frequency
    max_freq = max(counts.values())
    
    # Find how many tasks have exactly that maximum frequency
    max_freq_count = 0
    for count in counts.values():
        if count == max_freq:
            max_freq_count += 1
            
    # Calculate the minimum time required
    required_time = (max_freq - 1) * (n + 1) + max_freq_count
    
    # If the required time is less than the number of tasks, it means we don't need any idle time
    return max(len(tasks), required_time)

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the tasks array once to count the frequencies. Finding the max frequency and counting matches takes at most 26 operations. O(N) overall.

• Space complexity: O(1)

• Reason: We use an array/hash map of size at most 26.