621. Task Scheduler
Problem Description
In this problem, we are given an array of tasks where each type of task is represented by a letter. These tasks can be performed by a CPU in any sequence, where each task takes one unit of time to complete. However, there is a constraint: the CPU must wait for a cooldown period of n
units of time between performing the same type of task. During the cooldown period, the CPU can either perform a different task or remain idle if no other tasks are available. The goal is to find the minimum number of units of time the CPU will require to complete all tasks while adhering to the cooldown constraint.
Intuition
The key problem is to design a task schedule that minimizes idle time while respecting the cooldown constraint between the same tasks. To find the solution, we must first identify the task that occurs the most frequently, as it dictates the minimum time needed to complete all tasks.
Our solution approach begins by using a counter to count the occurrence of each task and find the maximum frequency (x
). The idea is to first schedule the most frequent tasks, ensuring that there are n
units of idle time between them. Once these are scheduled, we can fill in the remaining time with different tasks.
We calculate idle time using (x - 1) * (n + 1)
, where (x - 1)
represents the number of gaps between the most frequent tasks, and (n + 1)
represents the size of each gap including the task itself.
Then, we must account for tasks that occur as frequently as the most frequent task. We do this by adding s
, which is the number of tasks that have the maximum frequency. This ensures that if there are multiple tasks with the same maximum frequency, we have enough time slots to accommodate them without additional idle time.
Finally, we have two scenarios to consider:
-
The calculated time is greater than the total number of tasks. This means that even after scheduling the most frequent tasks with their cooldowns, we are able to accommodate all other tasks within the idle time slots. In this case, the calculated time is the result.
-
The calculated time is less than or equal to the number of tasks. This means that the tasks are diverse enough that we do not need idle time, and the total number of tasks is the minimum time needed to complete them all. In this case, the number of tasks is the result.
The max
function is used to choose the larger of the two scenarios above, which gives us the minimum units of time to finish all the tasks.
Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution approach involves the following steps detailed with the algorithms, data structures, and patterns used:
-
Counting Task Frequencies: Using Python's
Counter
class, we construct a frequency map which counts the number of occurrences for each task type. This helps us to quickly determine which tasks are the most frequent and how many times each one needs to be scheduled.cnt = Counter(tasks)
-
Identifying the Maximum Frequency: We need to know the frequency of the most common task because it will form the backbone of our scheduling strategy. The maximum value in our frequency map gives us this information.
x = max(cnt.values())
-
Calculating Idle Time Slots: Our goal is to minimize the CPU's idle time while respecting the cooldown period. The number of idle slots needed is based on the maximum frequency and the cooldown period. We calculate this with
(x - 1) * (n + 1)
, where(x - 1)
gives us the number of idle slots needed, assuming all slots are filled with the most frequent task and its subsequent cooldown periods. Adding1
accounts for the most frequent task itself being placed in the schedule. -
Determining the Number of Maximum Frequent Tasks: Since there might be multiple tasks that have the same maximum frequency, we calculate how many there are because they won't contribute to idle timeāthey can all be placed in the final unit of the cooldown period of the max frequency task without violating the cooldown requirement.
s = sum(v == x for v in cnt.values())
-
Calculating Total Time: Finally, we need to determine the total time which is the maximum of the length of the original task list or the calculated idle time slots plus the slots needed for the most frequent tasks.
return max(len(tasks), (x - 1) * (n + 1) + s)
Using this strategy efficiently arranges tasks and minimizes the idle time. Thus, the max
function is of particular importance here because it ensures that if no idle time is needed (i.e., there are enough less frequent tasks to fit in the cooldown periods), the total number of tasks is used. Otherwise, the calculated idle time and task slots indicate the CPU's total operating time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
In this example, let's consider an array of tasks represented as ['A', 'A', 'A', 'B', 'B', 'C']
and a cooldown period n = 2
.
-
Counting Task Frequencies: We count the occurrences of each task which gives us
{'A': 3, 'B': 2, 'C': 1}
. TaskA
appears three times,B
twice, andC
only once. -
Identifying the Maximum Frequency: The most common task is
A
, with a maximum frequency ofx = 3
. -
Calculating Idle Time Slots: With a cooldown period
n = 2
, we have(3 - 1) * (2 + 1) = 2 * 3 = 6
idle slots at first. These slots account for the time between completing instances of taskA
. -
Determining the Number of Maximum Frequent Tasks: In this case, there is only one task (
A
) that has the maximum frequency, sos = 1
. -
Calculating Total Time: Lastly, we must determine the actual total time:
The length of the original task list is
6
.Calculated time considering idle slots and the most frequent task is
6 (idle slots calculated in step 3) + 1 (task A itself) = 7
.We take the maximum:
max(6, 7) = 7
.
The scheduler might operate like this:
- Place task
A
- Idle slot
- Idle slot
- Place task
A
- Idle slot
- Idle slot
- Place task
A
- Place tasks
B
andC
(in the first two idle slots) - Place task
B
(in the last idle slot)
Thus, task A
sets the backbone for the scheduling, taking up the first slot, and all other tasks are arranged around the idle times initially allocated for A
. No additional idle time is needed because other tasks fill up the cooldown periods between A
s. In the end, the minimum number of time units the CPU requires to complete all tasks while respecting the cooldown period is 7
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def leastInterval(self, tasks: List[str], n: int) -> int:
5 # Count the occurrences of each task
6 task_counts = Counter(tasks)
7
8 # Find the maximum frequency of any task
9 max_freq = max(task_counts.values())
10
11 # Count how many tasks have the maximum frequency
12 max_freq_tasks_count = sum(freq == max_freq for freq in task_counts.values())
13
14 # Calculate the number of idle states needed, which is defined by the formula:
15 # (maximum frequency of any task - 1) * (n + 1) which gives the spaces between repetitions of the same task
16 idle_time = (max_freq - 1) * (n + 1)
17
18 # Add the count of most frequent tasks to idle time to get minimum length of the task schedule
19 min_length = idle_time + max_freq_tasks_count
20
21 # Return the maximum of the length of tasks (if no idle time is necessary) and calculated minimum length
22 return max(len(tasks), min_length)
23
1class Solution {
2 public int leastInterval(char[] tasks, int cooldown) {
3 // Counts of each task where index 0 represents 'A', 1 represents 'B', and so on.
4 int[] taskCounts = new int[26];
5 // Maximum frequency among the tasks
6 int maxFrequency = 0;
7
8 // Loop over the tasks to count them and find the task with maximum frequency.
9 for (char task : tasks) {
10 // Convert the task from char type to an index for our count array
11 int index = task - 'A';
12 // Increment the count for this task
13 taskCounts[index]++;
14 // Update the maximum frequency
15 maxFrequency = Math.max(maxFrequency, taskCounts[index]);
16 }
17
18 // Count how many tasks have the maximum frequency
19 int maxFrequencyTasks = 0;
20 for (int count : taskCounts) {
21 if (count == maxFrequency) {
22 maxFrequencyTasks++;
23 }
24 }
25
26 // Calculate the minimum length of the task schedule
27 // Each block of tasks includes the cooldown period followed by the most frequent task itself
28 // Then, add the number of tasks with maximum frequency to cover the last one without tailing idle time
29 int minScheduleLength = Math.max(tasks.length, (maxFrequency - 1) * (cooldown + 1) + maxFrequencyTasks);
30
31 return minScheduleLength;
32 }
33}
34
1class Solution {
2public:
3 int leastInterval(vector<char>& tasks, int coolingPeriod) {
4 vector<int> taskCount(26); // Initialize a vector to keep count of each task
5 int maxCount = 0; // Variable to keep track of the maximum count of a single task
6
7 // Count the tasks and find out the task with the maximum count
8 for (char task : tasks) {
9 task -= 'A'; // Convert char to an index between 0 and 25
10 ++taskCount[task]; // Increment the count for this task
11 maxCount = max(maxCount, taskCount[task]); // Update maxCount if current task's count is greater
12 }
13
14 // Count how many tasks have the same count as maxCount
15 int tasksWithMaxCount = 0;
16 for (int count : taskCount) {
17 if (count == maxCount) {
18 ++tasksWithMaxCount;
19 }
20 }
21
22 // Calculate the least interval
23 // First part: Calculate the minimum slots required based on the most frequent task (maxCount - 1) times (coolingPeriod + 1)
24 // Second part: Add the number of tasks that have the highest frequency (taskWithMaxCount)
25 int minSlotsRequired = (maxCount - 1) * (coolingPeriod + 1) + tasksWithMaxCount;
26
27 // The result is the maximum between the actual size of tasks and the minimum slots required
28 return max(static_cast<int>(tasks.size()), minSlotsRequired);
29 }
30};
31
1// This function computes the least number of time units required to complete all tasks
2// with a given cooling period between two same tasks.
3function leastInterval(tasks: string[], coolingPeriod: number): number {
4 const taskCount: number[] = new Array(26).fill(0); // Initialize an array to keep count of each task
5 let maxCount: number = 0; // Variable to keep track of the maximum count of a single task
6
7 // Count the tasks and find out the task with the maximum count
8 tasks.forEach(task => {
9 const index = task.charCodeAt(0) - 'A'.charCodeAt(0); // Convert char to an index between 0 and 25
10 taskCount[index]++; // Increment the count for this task
11 maxCount = Math.max(maxCount, taskCount[index]); // Update maxCount if current task's count is greater
12 });
13
14 // Count how many tasks have the same count as maxCount
15 let tasksWithMaxCount: number = 0;
16 taskCount.forEach(count => {
17 if (count === maxCount) {
18 tasksWithMaxCount++;
19 }
20 })
21
22 // Calculate the least interval
23 // First part: Calculate the minimum slots required based on the most frequent task (maxCount - 1) times (coolingPeriod + 1)
24 // Second part: Add the number of tasks that have the highest frequency (tasksWithMaxCount)
25 const minSlotsRequired: number = (maxCount - 1) * (coolingPeriod + 1) + tasksWithMaxCount;
26
27 // The result is the maximum between the actual size of the tasks and the minimum slots required
28 return Math.max(tasks.length, minSlotsRequired);
29}
30
Time and Space Complexity
The given Python function leastInterval
calculates the least time it would take to finish all tasks considering a cooldown period (n
intervals) between tasks that are the same. It uses Python Counter
from the collections
to achieve its purpose, following these steps:
-
Count each unique task and store the frequencies using
Counter(tasks)
. The time complexity of this operation isO(T)
, whereT
represents the total number of tasks, since it requires iterating over each task once. -
Find the maximum frequency
x
among all tasks withmax(cnt.values())
. The time complexity here isO(U)
, whereU
represents the number of unique tasks. -
Calculate the number of tasks with the maximum frequency, using list comprehension
sum(v == x for v in cnt.values())
. This is alsoO(U)
, the time needed to iterate over the unique task frequencies. -
Return the maximum between the actual number of tasks
len(tasks)
and a calculated value(x - 1) * (n + 1) + s
. The time complexity for this operation is constant,O(1)
.
The overall time complexity is dominated by the larger of O(T)
or O(U)
. Given that the number of unique tasks U
will always be less than or equal to the total number of tasks T
, the time complexity is O(T)
.
As for the space complexity:
-
Counter(tasks)
constructs a hashmap to store the task frequencies, consumingO(U)
space, whereU
is the number of unique tasks. -
The space for storing maximum frequency
x
and the summations
is constant,O(1)
. -
The temporary list comprehension used for the summation does not require additional space as it is computed inline and summed immediately.
Therefore, the space complexity of the function is O(U)
.
Overall, the time complexity is O(T)
and the space complexity is O(U)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Donāt Miss This!