Design a task scheduler in Python.
Medium
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
Time 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).
Interview experiences
2 sharedRelated courses
