“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Title 1

Leetcode 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, 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 1:

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

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 this

Example 2:

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) – > A

 

Tip:

1 <= task.length <= 104 Tasks [I] Is an uppercase letter. The value of n ranges from 0 to 100.

Analysis of the

  • Suppose you have A set of tasks [A,A,A,A,B,B,B,C,C,C]
  • It can be seen from the listing that we should arrange task A with the maximum number of tasks first

  • Then, another type of task B is inserted into the interval after task A is arranged to avoid being together with the task

  • At this point, insert the C task into the remaining position

  • The same task will have time interval, insert other tasks can save time
  • Any task with a number greater than 1 should be aligned with the maximum number of task intervals
  • Of course, if n is 0, the execution time is the number of tasks

  • This is 3 times 3 plus 1

  • In this case, it’s 3 times 3 plus 2

  • Combining the two figures, it can be drawn that the time is related to the maximum number of tasks szie, the maximum type of tasks M and the interval n

  • szie - 1 * n + 1 + m

Code implementation

/** * @param {character[]} tasks * @param {number} n * @return {number} */ // lodash.js var leastInterval = Function (tasks, n) {let freq = _. CountBy (tasks) // maxNumsTask = math.max (tasks, n) {let freq = _. Object.values(freq)) let m = 0 object.values (freq).foreach (v => {if(v === maxNumsTask){m++}}) // Compare the relationship between the total number of tasks and the shortest time return Math.max((maxNumsTask-1)*(n+1)+m,tasks.length) };Copy the code