Task Scheduler medium

Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, and an integer n, representing the cooldown period between two same tasks (i.e., between two same characters). You need to return the least number of intervals the CPU will take to finish all the tasks.

Example 1

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

Output: 8

Explanation: A -> B -> A -> B -> A -> B -> idle -> A (A -> B -> idle -> A -> B -> idle -> A -> B)

There are 3 'A's and 3 'B's. The optimal solution requires 8 intervals.

Example 2

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

Output: 6

Explanation: Since n=0, there is no cooldown period. We can execute all tasks consecutively.

Steps

1. Frequency Count: Count the frequency of each task using a dictionary or counter.
2. Find Max Frequency: Identify the task with the maximum frequency. Let's call this max_freq.
3. Count Max Frequency Tasks: Determine the number of tasks with the max_freq. Let's call this max_freq_count.
4. Calculate Idle Slots: The number of idle slots needed is calculated as (max_freq - 1) * (n + 1). This is because for each task with the maximum frequency, we need n idle slots between consecutive occurrences of that task. We subtract 1 from max_freq because the last occurrence doesn't need an idle slot after it.
5. Handle Remaining Tasks: After placing the high-frequency tasks with their idle slots, there might be some remaining tasks. We need to add the number of these remaining tasks to the total time.
6. Total Time: The total time is the maximum of the idle slots plus the total number of tasks and the total number of tasks itself. This accounts for the scenario where there aren't enough other tasks to fill the idle slots.

Explanation

The core idea is to schedule the most frequent tasks as far apart as possible to minimize the total execution time. By strategically placing idle slots between the most frequent tasks, we ensure that we don't violate the cooldown constraint. The formula for idle slots cleverly calculates the necessary spacing to accommodate the cooldown period.

Code

from collections import Counter

def leastInterval(tasks, n):
    """
    Calculates the minimum number of intervals to complete all tasks.

    Args:
        tasks: A list of characters representing the tasks.
        n: The cooldown period between two same tasks.

    Returns:
        The minimum number of intervals.
    """

    task_counts = Counter(tasks)
    max_freq = max(task_counts.values())
    max_freq_count = sum(1 for count in task_counts.values() if count == max_freq)
    idle_slots = (max_freq - 1) * (n + 1)
    remaining_tasks = len(tasks) - max_freq_count * max_freq

    return max(len(tasks), idle_slots + remaining_tasks)

Complexity

• Time Complexity: O(N), where N is the number of tasks. This is dominated by the frequency counting and the loop to count tasks with maximum frequency.
• Space Complexity: O(1), as the space used by the counter is limited to the number of unique tasks (which is usually a small constant in practice, not dependent on input size). In worst case it can be O(N) if number of unique tasks is close to N. However for the given problem constraints, O(1) is a reasonable assessment.