Task Scheduler Interview Question for Google

import heapq
from collections import Counter


def leastInterval(tasks, n):
    # Count the frequency of each task
    task_counts = Counter(tasks)

    # Use a max heap to store the frequencies
    max_heap = [-count for count in task_counts.values()]
    heapq.heapify(max_heap)

    time = 0
    queue = []  # (available_time, task_count)

    while max_heap or queue:
        time += 1

        if max_heap:
            count = heapq.heappop(max_heap)
            count += 1  # Decrement count (since it's negative)

            if count != 0:
                queue.append((time + n, count))  # Add to cooling queue

        if queue and queue[0][0] == time:
            heapq.heappush(max_heap, queue[0][1])  # Add back to available tasks
            queue.pop(0)

    return time

# Example usage:
tasks1 = ["A","A","A","B","B","B"]
n1 = 2
print(f"Example 1: tasks={tasks1}, n={n1}, result={leastInterval(tasks1, n1)}") # Output: 8

tasks2 = ["A","C","A","B","D","B"]
n2 = 1
print(f"Example 2: tasks={tasks2}, n={n2}, result={leastInterval(tasks2, n2)}") # Output: 6

tasks3 = ["A","A","A", "B","B","B"]
n3 = 3
print(f"Example 3: tasks={tasks3}, n={n3}, result={leastInterval(tasks3, n3)}") # Output: 10

Explanation:

Count Task Frequencies: Use a Counter to determine how many times each task appears.
Max Heap: Utilize a max heap (priority queue) to store the frequencies of the tasks. This allows us to always pick the most frequent task available.
Cooling Queue: A queue queue is used to keep track of tasks that are in their cooling period. Each entry in the queue is a tuple of (available_time, task_count), where available_time is the time when the task can be re-added to the max heap, and task_count is the updated count of the task.
Main Loop:
- Increment the current time.
- If there are tasks in the max heap, pop the most frequent task (smallest negative count).
- Decrement the count of the task (increment, since it is stored as negative).
- If the count is not zero, add the task to the cooling queue with its available time.
- If there are tasks in the cooling queue and their available time is equal to the current time, add them back to the max heap.
Return Time: The loop continues until both the max heap and the cooling queue are empty, at which point the total time is returned.

Alternative Solution (Math-Based):

def leastInterval_math(tasks, n):
    task_counts = Counter(tasks)
    max_count = max(task_counts.values())
    max_count_tasks = sum(1 for count in task_counts.values() if count == max_count)

    idle_slots = (max_count - 1) * (n + 1)
    available_tasks = len(tasks) - max_count * max_count_tasks
    idle_slots = max(0, idle_slots - available_tasks)

    return len(tasks) + idle_slots


tasks1 = ["A","A","A","B","B","B"]
n1 = 2
print(f"Example 1 (Math): tasks={tasks1}, n={n1}, result={leastInterval_math(tasks1, n1)}") # Output: 8

tasks2 = ["A","C","A","B","D","B"]
n2 = 1
print(f"Example 2 (Math): tasks={tasks2}, n={n2}, result={leastInterval_math(tasks2, n2)}") # Output: 6

tasks3 = ["A","A","A", "B","B","B"]
n3 = 3
print(f"Example 3 (Math): tasks={tasks3}, n={n3}, result={leastInterval_math(tasks3, n3)}") # Output: 10

Explanation:

Count Task Frequencies: Use Counter to count task frequencies.
Identify Most Frequent Task: Find the maximum frequency (max_count) and the number of tasks with this frequency (max_count_tasks).
Calculate Idle Slots: Calculate the number of idle slots needed to satisfy the cooling interval constraint for the most frequent tasks: (max_count - 1) * (n + 1). This is because each of the max_count - 1 occurrences of the most frequent task requires n idle slots after it.
Adjust Idle Slots: Reduce the idle slots by the number of available tasks (available_tasks), which are tasks that aren't the most frequent ones. available_tasks = len(tasks) - max_count * max_count_tasks
Ensure Non-Negative Idle Slots: Make sure the number of idle slots is not negative using max(0, idle_slots - available_tasks). A negative value would mean there are enough other tasks to fill the idle slots.
Calculate Total Time: The total time is the sum of the number of tasks and the number of idle slots: len(tasks) + idle_slots.

Big O Analysis:

Heap-Based Solution:

Time Complexity: O(N log K), where N is the number of tasks and K is the number of unique tasks. The Counter operation is O(N). The heap operations (push and pop) take O(log K) time, and in the worst case, we might perform these operations for each task. Thus, the overall time complexity is O(N log K).
Space Complexity: O(K), where K is the number of unique tasks. The Counter and the heap store at most K unique tasks.

Math-Based Solution:

Time Complexity: O(N), where N is the number of tasks. The Counter operation takes O(N) time. Finding the maximum count and the number of tasks with the maximum count also take O(N) time. Thus, the overall time complexity is O(N).
Space Complexity: O(K), where K is the number of unique tasks. The Counter stores at most K unique tasks.

Edge Cases:

Empty Task List:
- If the input tasks list is empty, the function should return 0.
Zero Cooling Interval (n = 0):
- If n is 0, the function should return the number of tasks, as there is no cooling period.
Large Cooling Interval:
- If n is very large compared to the number of tasks, the algorithm should correctly calculate the number of idle slots required.
Tasks are all unique:
- If all tasks are unique, no idle time is needed and the result should equal the number of tasks.
All Tasks are Same:
- If all the tasks are the same, the result should equal len(tasks) + (len(tasks) - 1) * n.
Mixed Task Types:
- The solution handles mixed task types with varying frequencies by prioritizing tasks with higher frequencies to minimize idle time.