LeetCode Solutions Blog

Task Scheduler

Number: 621

Difficulty: Medium

Paid? No

Problem Description

Given a list of tasks (each represented by an uppercase letter) and a cooling interval n, determine the minimum number of CPU intervals required to execute all tasks such that the same task is separated by at least n intervals. In these intervals, the CPU can either execute a task or remain idle.

Key Insights

Count the frequency of each task.
The task with the highest frequency determines the base structure.
Identify how many tasks share the maximum frequency.
Calculate the total time based on the formula: max(total tasks, (max frequency - 1) * (n + 1) + count of tasks with maximum frequency).
This approach avoids simulating the entire scheduling by using a greedy strategy.

Space and Time Complexity

Time Complexity: O(N) where N is the number of tasks (counting frequency, then iterating over constant 26 letters). Space Complexity: O(1) since the frequency count uses an array or hash map with fixed size (26 letters).

Solution

We first count the frequency of each task. The task(s) with the maximum frequency establish the minimum structure required. Compute the ideal idle slots based on the count of these maximum tasks and the cooling period n. Finally, compare this computed length with the total number of tasks to get the final answer. This greedy strategy avoids explicit simulation and leverages mathematical formulation.

Code Solutions

# Python solution for Task Scheduler
from collections import Counter

def leastInterval(tasks, n):
    # Count the frequency of each task
    task_counts = Counter(tasks)
    # Find the maximum frequency among tasks
    max_freq = max(task_counts.values())
    # Count how many tasks have the maximum frequency
    max_count = sum(1 for count in task_counts.values() if count == max_freq)
    
    # Calculate the minimum intervals required based on the most frequent tasks
    part_count = max_freq - 1                   # Number of parts between the most frequent task
    part_length = n - (max_count - 1)             # Effective empty slots per part after placing max frequency tasks
    empty_slots = part_count * part_length        # Total empty slots to fill with idle or other tasks
    available_tasks = len(tasks) - max_freq * max_count  # Remaining tasks to fill the empty slots
    idles = max(0, empty_slots - available_tasks) # Remaining idle slots if available tasks are not enough
    
    # The total intervals is the sum of all tasks and idle slots inserted
    return len(tasks) + idles

# Example usage:
if __name__ == "__main__":
    tasks1 = ["A","A","A","B","B","B"]
    n1 = 2
    print(leastInterval(tasks1, n1))  # Output: 8