To the chase

621. Task scheduler

You are given a list of tasks that the CPU needs to perform represented by the character array Tasks. Each letter represents a different kind of task. Tasks can be executed in any order, and each task can be completed in one unit of time. At any given unit of time, the CPU can complete a task or be on standby.

However, there must be a cooling time of integer length ****n **** between two tasks of the same kind, so that there are at least n consecutive units of time for the CPU to perform different tasks, or to be on standby.

You need to calculate the minimum time required to complete all the tasks.

Example 1:

Input: the tasks = [" A ", "A", "A", "B", "B", "B"), n = 2 output: 8: A -> B -> (Standby) -> A -> B -> (Standby) -> A -> B -> A -> B in this example, two tasks of the same type must be separated by A cooldown of length n = 2, and only one unit of time is required to perform A task, so the (standby) state appears in the middle.Copy the code

Example 2:

Input: the tasks = [" A ", "A", "A", "B", "B", "B"), n = 0 output: 6: In this case, the arrangement of any size is 6 can meet the requirements, because n = 0 [" A ", "A", "A", "B", "B", "B"] [" A ", "B", "A", "B", "A", "B"] [" B ", "B", "B", "A", "A", "A"]... Such as thisCopy the code

Example 3:

Input: the tasks = [" A ", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"], n = 2 output: 16 explanation: one possible solution is to: - A - > B > C - > A - > D - > E - > A - > F - > G - > A - > (standby) - > (standby) - > A - > (standby) - > (standby) - > ACopy the code

Resolution:

N is the cooldown time, which means that the same task must wait n time units before it can be performed again, but other tasks can be performed in this period of time. Similarly, each same task must wait N time units.

Greedy principle

Suppose we only have one task, A, with m tasks and A cooldown of n, what is the time it takes?

M = 3, so it takes (3-1) * (n + 1) + 1 time unit, that is, (m-1) * (n + 1) + 1

What if we add task B to the task list?

You can see that the time it takes hasn’t changed. The reason is that B takes up the original standby time, so the total time will not change. Assuming that A is the one that needs to be executed the most times, can we assume that the minimum time it needs is the formula above:

(A Number of executions -1) * (n + 1) + 1

The reason is simple, you have to execute all of the A’s, and that’s the minimum cost. So the minimum consumption that is performed the most times, is the least likely to be consumed of all the tasks. The real result will only be greater than or equal to this number.

Therefore, the greedy principle is: the required time is only related to the task with the highest number of repetitions, and the result is greater than or equal to (the highest number of repetitions of the task -1) * (n + 1) + 1

When does it get bigger than that?

Let’s try animating it:

It can be seen from the animation that if the frequency of other tasks is the same as that of A, the frequency will be + 1. A is the task with the maximum frequency, so it is unnecessary to consider the task with A higher frequency.

Suppose there’s another task C, which is the same number of times as A? So plus 2, so we also need to find the number of frequencies that are equal to the highest frequency.

Try to achieve

First define the variables we need:

Let obj = {} // key task value Number of occurrences let maxCount = 0 // Number of occurrences with the highest frequency let equalCount = 0 // Number of occurrences with the highest frequencyCopy the code

Figure out the number of tasks with the highest frequency:

for(let index = 0 ; index < tasks.length ; index++) {
        obj[tasks[index]] = obj[tasks[index]] ? obj[tasks[index]] + 1 : 1
    }
    const keys = Object.keys(obj)
    maxCount = obj[keys[0]]
    for (let index = 1 ; index < keys.length ; index++) {
        const key = keys[index]
        if (maxCount < obj[key]) {
            maxCount = obj[key]
        }
    }
Copy the code

EqualCount equalCount = equalCount

for(let index = 0 ; index < tasks.length ; index++) { obj[tasks[index]] = obj[tasks[index]] ? obj[tasks[index]] + 1 : 1 } const keys = Object.keys(obj) maxCount = obj[keys[0]] for (let index = 1 ; index < keys.length ; index++) { const key = keys[index] if (maxCount < obj[key]) { maxCount = obj[key] equalCount = 0 } else if (maxCount ===  obj[key]) { equalCount++ } }Copy the code

Final return formula

return (maxCount - 1) * (n + 1) + 1  + equalCount
Copy the code

Submit with confidence!

The discovery didn’t pass. We must have missed something.

To find the reason

There are two obvious problems:

  1. If n = 0, isn’t the time spent the length of tasks?
  2. How can the calculated time be shorter than the length of tasks?

It should take longer than the number of tasks. If there is no cooldown, it should take at least one unit of array length!

So when the calculated time is less than the theoretical minimum time, we take the minimum time for tasks.

return Math.max((maxCount - 1) * (n + 1) + 1 + equalCount, tasks.length)

Finally, a smile of relief.

Complete code:

/** * @param {character[]} tasks * @param {number} n * @return {number} */ var leastInterval = function(tasks, N) {let obj = {} // let maxCount = 0 // let equalCount = 0 for(let index = 0;  index < tasks.length ; index++) { obj[tasks[index]] = obj[tasks[index]] ? obj[tasks[index]] + 1 : 1 } const keys = Object.keys(obj) maxCount = obj[keys[0]] for (let index = 1 ; index < keys.length ; index++) { const key = keys[index] if (maxCount < obj[key]) { maxCount = obj[key] equalCount = 0 } else if (maxCount ===  obj[key]) { equalCount++ } } return Math.max((maxCount - 1) * (n + 1) + 1 + equalCount, tasks.length) }; // A -> . -> . -> A -> . -> . -> ACopy the code