algoadvance

The problem “621. Task Scheduler” on LeetCode can be described as follows:

You are given a char array representing tasks CPU needs to do. It contains uppercase English letters where different letters represent different tasks. Tasks could be done without original 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. That means if you have two same tasks, there must be at least n units of time between them.

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

Example:

Clarifying Questions

  1. Can there be any lowercase letters in the input?
    • No, only uppercase English letters are given.
  2. Can n be negative?
    • No, n is a non-negative integer.
  3. Can the array of tasks be empty?
    • No, the array will have at least one task.

Code

from collections import Counter

def leastInterval(tasks, n):
    task_counts = Counter(tasks)
    max_freq = max(task_counts.values())
    
    # Find the number of tasks that have the max frequency
    max_freq_tasks = sum(1 for task, count in task_counts.items() if count == max_freq)
    
    intervals_needed = (max_freq - 1) * (n + 1) + max_freq_tasks
    
    return max(intervals_needed, len(tasks))

# Example usage:
tasks = ["A", "A", "A", "B", "B", "B"]
n = 2
print(leastInterval(tasks, n))  # Output: 8

Strategy

  1. Count Task Frequencies:
    • Use a Counter to count the frequency of each task.
  2. Determine the Maximum Frequency:
    • Identify the maximum frequency of any task.
  3. Calculate Intervals Required:
    • Calculate the minimum number of intervals required using the formula: [ \text{intervals_needed} = (\text{max_freq} - 1) \times (n + 1) + \text{max_freq_tasks} ]
    • Here, (\text{max_freq} - 1) gives the number of full cycles we will have with the most frequent tasks, and n + 1 gives the total slots needed for each cycle. max_freq_tasks accounts for additional slots needed if there are multiple tasks with the maximum frequency.
  4. Return the Maximum of Calculated Intervals and Length of Tasks:
    • Sometimes, the total number of tasks itself would require more intervals than the calculated intervals due to overlapped or fewer constraints of cooldown periods.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com