Task Scheduler - LeastInterval LeetCode Problem

Javascript

Recently I found this Task Scheduler problem in leetcode and looks like a really interesting problem to be solved.

Here’s the link to the exercise https://leetcode.com/problems/task-scheduler/

Let’s read the description

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.
Return the least number of units of times that the CPU will take to finish all the given tasks.

Here’s an example of the return

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

As always, there are different ways to solve this exercise, here I’m just gonna show one of them.

Let’s analyze the problem first.

1. We’re receiving an array of characters. each letter is a task.
2. n represents the number of spaces required between repeated letters.
3. We need to found the minimum value ..

Let’s take the first example and analyze it.

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

if n = 0 that means that the space between repeated letters is 0, in which case the response is equal to the array length (example 2).

if n = 2 the result is 8, but why?

A -> B -> idle -> A -> B -> idle -> A -> B => length equal to 8

Let’s take a look at the array

A B
A B
A B

we have 3 groups of the AB, however as n=2 we need to add an idle space between the two first rows

A B idle
A B idle
A B

Now we have 2 rows with length of 3 and one of length of 2. Now the total of elements is 8. There is our answer.

A B idle --> length 3
A B idle --> length 3
A B      --> length 2
2 rows * 3 + 1 row * 2

Before we generalize, lets see another example

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"]
n = 2
Output: 16
A  B    C --> length 3
A  D    E --> length 3
A  F    G --> length 3
A  idle idle --> length 3
A  idle idle --> length 3
A --> length 1
5 rows * 3 + 1 row * 1 => 16
note: as n is 2 we need two letters between two A

Now let’s make some generalizations

* Maximum number of rows is equal to the most repeated task (or letter)
* The length of the rows - 1 is equal to the repeated letter plus the number of spaces required (n), that means the value of the length is equal n+1 
* We need to sum the length of the last row

Now we have a little formula to get the answer we need

(TotalRows - 1) * (n+1) + lastRowLength

Let’s code

1. Get the frequencies of each letter.
2. Get the max value of the frequencies.
3. Get the length of the minimum

Disclaimer: I’m gonna use javascript to code the response

An easy way to get the frequencies is using a reducer function. We are creating a map and adding one each time a letter appears

Input: tasks = ["A","A","A","B","B","B"], n = 2

const newMap = tasks.reduce((map, obj)=> {
    map[obj] = map[obj] + 1 || 1 ;
    return map;
}, {});
// the result is an object like this {A:3,B:3}

Now let’s get an array of the values.

const array=Object.values(newMap)
// the result is an array [3,3]

Now that we have the frequencies let’s get the maximum number of frequencies that is equivalent to the maximum number of rows .

const maximumRows = Math.max(...array) 
// result = 3

Now we need the length of the last row. For that we are going to use a filter and get the length of the resultant array.

const lastRowLength = array.filter(x => x == maximumRows).length
// result 2

How this works?
After we got the frequencies we need to look for the number of repetitions of the max value, let’s see an example.

[A,A,A,B,B,B]
frequencies -> [3,3]
Max -> 3
* How many 3 do we have in the array? -> 2 
that's the length of the last line
A B idle -> length 3
A B idle -> length 3
A B      -> length 2

Now the result is just

(maximumRows - 1) * (n + 1) + lastRowLength
// result 8

Now, we’re almost done, but remember we have a case when n might be 0, and we need to face it.

There are two possibilities you can whether create a conditional or use the max function

if (n===0) return tasks.length
or
Math.max(tasks.length, (maximumRows - 1) * (n + 1) + minimumRows)

The final code could be…

const leastInterval = (tasks, n)=> {
 const newMap = tasks.reduce((map, obj)=> {
    map[obj] = map[obj] + 1 || 1 ;
    return map;
  }, {});
     
const array=Object.values(newMap)
const maximumRows = Math.max(...array)
const lastRowLength = array.filter(x => x === maximumRows).length
return Math.max(tasks.length, (maximumRows - 1) * (n + 1) + lastRowLength) 
};

I hope you’ve enjoyed.

Keep coding!