Topic:
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, two tasks of the same kind must have a cooling time of integer length n between them, so that there are at least n consecutive units of time for which the CPU is performing different tasks or is on standby.
You need to calculate the minimum time required to complete all the tasks.
Example:
- Example 1:
Enter: tasks = ["A"."A"."A"."B"."B"."B"], n = 2
Output: 8
Explanation: A -> B -> (standby) -> A -> B -> (standby) -> A -> B
In this example, two tasks of the same type must be separated by a cooldown of length n = 2, and it only takes one unit of time to execute a task, so the (standby) state occurs in the middle.
Copy the code- Example 2:
Enter: tasks = ["A"."A"."A"."B"."B"."B"], n = 0
Output: 6
Explanation: In this case, any permutation of size 6 will suffice because n = 0
["A"."A"."A"."B"."B"."B"]
["A"."B"."A"."B"."A"."B"]
["B"."B"."B"."A"."A"."A"]
.
Such as this
Copy the code- Example 3:
Enter: tasks = ["A"."A"."A"."A"."A"."A"."B"."C"."D"."E"."F"."G"], n = 2
Output: 16
Explanation: One possible solution is:
- A - > B > C - > A - > D - > E - > A - > F - > G - > A - > (standby) - > (standby) - > A - > (standby) - > (standby) - > A
Copy the codeTip:
- 1 <= task.length <=
- Tasks [I] is a capital English letter
- The value of n ranges from 0 to 100.
The topic
Ideas:
An array of tasks, each element executed at least n steps apart, returns the minimum number of steps required to complete the execution
In order to minimize the number of execution steps, it is necessary to reduce the number of standby, so it is necessary to find the task that needs to be executed for the most times first, and place other tasks in its execution interval. Then, if the maximum number of tasks is enough, the number of steps is Max *(n+1).
Interval n The interval between two tasks of the same type is expressed in n+1
It is assumed that the maximum number of tasks is enough, and in fact the last interval is not necessarily filled with tasks, so we need to know which task in the last n cycle has the least number of steps:
- Tasks whose number of repetitions is less than Max are prioritized in the cycle before the last one and can be completed
- Multiple tasks may be repeated Max, so the repeated tasks need to be arranged in the last cycle
/ * *
* @param {character[]} tasks
* @param {number} n
* @return {number}
* /
var leastInterval = function(tasks, n) {
const len = tasks.length
if (n === 0) return len
let max = 0.
map = new Map(),
maxNum = 0
// Count the number of occurrences
for (let i = 0; i < len; i++) {
const num = map.get(tasks[i]) || 0
map.set(tasks[i], num + 1)
max = Math.max(max, num + 1)
}
// The maximum number of tasks can be multiple
for (let value of map.values()) {
if (value === max) maxNum++
}
// Minimum number of steps to execute
return Math.max((max - 1) * (n + 1) + maxNum, len)
}
Copy the codeBlog: Front end little bookboy
Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message
Public number: front end little bookboy