Task Scheduler
You are given a list of tasks where each task is represented by a character. Each task must be performed in a sequence, and you need to ensure that the same task is not executed again until after a cooldown period of n intervals. The goal is to determine the minimum number of intervals required to complete all tasks, including any idle time required to respect the cooldown period.
Write a function leastInterval that returns the minimum number of intervals required to execute all tasks while respecting the cooldown period n.
Examples
tasks = ['A', 'A', 'A', 'B', 'B', 'B'] n = 2 output: 8
To execute all tasks while respecting the cooldown period of 2, the schedule could be ['A', 'B', 'idle', 'A', 'B', 'idle', 'A', 'B']. This schedule allows each task to be performed and includes idle intervals where necessary to respect the cooldown period. Thus, the minimum number of intervals required is 8.
tasks = ['A', 'A', 'A', 'B', 'B', 'B'] n = 0 output: 6
With a cooldown period of 0, there is no idle time needed. Thus, the minimum number of intervals is equal to the number of tasks, which is 6.
Our solution determines the minimum number of intervals required to complete all tasks while respecting a cooldown period n. The approach is based on the following key steps:
-
Count Task Frequencies: We first count the frequency of each task using a hash map (
task_counts). This helps us identify the maximum number of times any single task appears. -
Determine Maximum Frequency and Task Count: We identify the task that appears the most frequently (
maxCount) and count how many tasks have this maximum frequency (maxCountTasks). -
Calculate Required Idle Slots: We calculate the number of idle slots needed between the most frequent tasks to ensure they are spaced out according to the cooldown period. This is done using the formula:
partCount = maxCount - 1partLength = n - (maxCountTasks - 1)emptySlots = partCount * partLength
-
Compute Available Tasks: We compute the total number of tasks that can be filled into these empty slots:
availableTasks = totalTasks - maxCount * maxCountTasks
-
Calculate Idle Time: We determine the total number of idle intervals required:
idles = max(0, emptySlots - availableTasks)
-
Compute Total Intervals: Finally, we return the total number of intervals needed:
totalIntervals = totalTasks + idles
In the task scheduler problem, "parts" or "partitions" refer to the segments or gaps created between the occurrences of the most frequent tasks to respect the cooldown period n. By calculating the number of such partitions needed (partCount = maxCount - 1) and their length (partLength = n - (maxCountTasks - 1)), we ensure that tasks are spaced out correctly. The total number of intervals is then determined by filling these partitions with other tasks or idle slots, ensuring the schedule adheres to the cooldown requirements.
from typing import List
def least_interval(tasks: List[str], n: int) -> int:
task_counts = {}
for task in tasks:
if task in task_counts:
task_counts[task] += 1
else:
task_counts[task] = 1
max_count = max(task_counts.values())
max_count_tasks = sum(1 for count in task_counts.values() if count == max_count)
part_count = max_count - 1
part_length = n - (max_count_tasks - 1)
empty_slots = part_count * part_length
available_tasks = len(tasks) - max_count * max_count_tasks
idles = max(0, empty_slots - available_tasks)
return len(tasks) + idlesTime Complexity: The solution has a time complexity of O(n), where n is the number of tasks. This is because we traverse the list of tasks a few times, performing constant-time operations for each element.
Space Complexity: The space complexity is O(1) if we disregard the input size since the hash map for task counts will store at most 26 entries (one for each possible task).
import time
class Task: def __init__(self, description, interval=None): self.description = description self.interval = interval self.next_run = time.time()
class SimpleTaskScheduler: def __init__(self): self.tasks = []
def add_task(self, description, interval=None): self.tasks.append(Task(description, interval)) def run(self, duration=60): end_time = time.time() + duration while time.time() < end_time: current_time = time.time() for task in self.tasks: if current_time >= task.next_run: print(f"Running task: {task.description}") if task.interval: task.next_run = current_time + task.interval else: self.tasks.remove(task) time.sleep(1)# Example usage if __name__ == "main": scheduler = SimpleTaskScheduler()
scheduler.add_task("One-time task") scheduler.add_task("Recurring task every 5 seconds", 5) scheduler.add_task("Another recurring task every 3 seconds", 3) scheduler.run(duration=20) # Run for 20 seconds