Task Scheduler

Try to solve the Task Scheduler problem.

We'll cover the following

Statement#

We’re given a character array, tasks, where each character represents a unique task. These tasks need to be performed by a single CPU, with each task taking one unit of time. The tasks can be performed in any order. At any given time, a CPU can either perform some task or stay idle.

For the given tasks, we are also provided with a positive integer value, n, which represents the cooling period between any two identical tasks. This means that the CPU must wait for at least n units of time before it performs the same task again. For example, if we have the tasks [A,B,A,C][A, B, A, C] and n = 2, then after performing the first AA task, the CPU will wait for at least 2 units of time to perform the second AA task. During these 2 units of time, the CPU can either perform some other task or stay idle.

Given the two input values, tasks and n, find the least number of units of time the CPU will take to perform the given tasks.

Constraints:

  • 1≤ 1 \leq  tasks.length ≤1000 \leq 1000

  • tasks consists of uppercase English letters.

  • 0≤0 \le n ≤100 \leq 100

Examples#

Let’s take a look at a few examples to get a better understanding of the problem statement:

Created with Fabric.js 3.6.6 Tasks A A B B A B Idle A B n = 2 Input Output Units of time = 5 We scheduled tasks A and B in this manner to get to the minimum number of units of time. ----------------------------------------------------------------------- Sample Example 1

1 of 3

Created with Fabric.js 3.6.6 Tasks A B A A B C A B C Idle A B Idle Idle A n = 3 Input Output Units of time = 9 We first scheduled all the A tasks, then all the B tasks and lastly all of the C tasks to get to the minimum number of units of time. Sample Example 2 ---------------------------------------------------------------------------------------------------------

2 of 3

Created with Fabric.js 3.6.6 Tasks A C B A Note: Here, we can have any permutation of size 4 since n = 0.For example: [A,B,C,A], [A,B,A,C], [B,C,A,A], [C,B,A,A], [A,A,C,B] n = 0 B A C A Input Output Units of time = 4 As n = 0, it will have zero effect on CPU's processing time. Therefore, we can schedule the tasks in any way we want. Sample Example 3 ---------------------------------------------------------------------------

3 of 3

Understand the problem#

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Task Scheduler

1

What is the minimum number of units of time if the following values are given as input?

Tasks = [A, A, A, B, B, C, C]

n = 1

A)

3

B)

7

C)

8

D)

9

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Count and store the frequencies of all the tasks.

Sort the frequencies.

Start scheduling the tasks in the descending order of their frequencies, and compute the idle time during the process.

The total time can be calculated as the sum of the number of tasks and the idle time.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 A node_11 A node_21 B node_31 B
Visualization for Input #1
Task Scheduler

Solution: Merge Intervals

Solution: Task Scheduler