“This is the second day of my participation in the First Challenge 2022.

preface

Today we will calculate a task for the CPU required the shortest time, first follow the topic hard just once, found in my layman here is also ok, I do not understand what greedy algorithm of what, is dry.

Topic describes

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.

Source: LeetCode link: leetcode-cn.com/problems/ta… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

title

  1. In the task array are our tasks, and if the tasks are the same, they will take n units of cooldown to execute
  2. In the best case, the cooldown time between each repetition element is filled up by other tasks, so we can get the shortest time by knowing the task with the most repetitions (maxExc) : maxExc * (n+1)
  3. But we need to take into account the occupied case, and if we look at the figure above, we can see that the last row of tasks, when n=2, actually only performs the previous task, and then we don’t calculate the cooldown time,So how do you get the number of tasks in the last row?

    1) Calculate the number of tasks of the same type equal to maxExc, and count the number as maxCount

    2) the shortest time is :(maxexc-1) * (n + 1) + maxCount
  4. The minimum task time cannot be shorter than the number of tasks.Task.length = n=0
  5. Does our formula (maxex-1) * (n + 1) + maxCount calculate the number of tasks less than the number of tasks? This situation must be ruled out
    • For example, in the second diagram, when n=1, A and B are the most repeated substitutions:

    (4-1) * (1+1) + 2 = 8 < task.length = 9

To the problem solving

/** * @param {character[]} tasks * @param {number} n * @return {number} */ var leastInterval = function(tasks, n) { const sortObj = _.countBy(tasks); / / 1, here is the number of jobs classification and counting, such as: [' A ', 'A', 'B'] = > {2, A: B: 1} const maxExc = math.h Max (... Object.values(sortObj)); Let maxCount = 0; let maxCount = 0; If (count === maxExc) {maxCount++; if(count == maxExc) {maxCount++; } }) return Math.max((maxExc-1)*(n+1) + maxCount, tasks.length); // The minimum time can't be less than task.length; };Copy the code