621. Task Scheduler

MediumGreedyArrayHash TableCountingSortingHeap (Priority Queue)
Leetcode Link

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:

  1. 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.

  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The solution approach involves the following steps detailed with the algorithms, data structures, and patterns used:

  1. 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.

    1cnt = Counter(tasks)

  2. 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.

    1x = max(cnt.values())

  3. 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. Adding 1 accounts for the most frequent task itself being placed in the schedule.

  4. 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.

    1s = sum(v == x for v in cnt.values())

  5. 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.

    1return 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example 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.

  1. Counting Task Frequencies: We count the occurrences of each task which gives us {'A': 3, 'B': 2, 'C': 1}. Task A appears three times, B twice, and C only once.

  2. Identifying the Maximum Frequency: The most common task is A, with a maximum frequency of x = 3.

  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 task A.

  4. Determining the Number of Maximum Frequent Tasks: In this case, there is only one task (A) that has the maximum frequency, so s = 1.

  5. 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 and C (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 As. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following shows the order of node visit in a Breadth-first Search?

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:

  1. Count each unique task and store the frequencies using Counter(tasks). The time complexity of this operation is O(T), where T represents the total number of tasks, since it requires iterating over each task once.

  2. Find the maximum frequency x among all tasks with max(cnt.values()). The time complexity here is O(U), where U represents the number of unique tasks.

  3. Calculate the number of tasks with the maximum frequency, using list comprehension sum(v == x for v in cnt.values()). This is also O(U), the time needed to iterate over the unique task frequencies.

  4. 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:

  1. Counter(tasks) constructs a hashmap to store the task frequencies, consuming O(U) space, where U is the number of unique tasks.

  2. The space for storing maximum frequency x and the summation s is constant, O(1).

  3. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

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

Heap Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ