[topic address]

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: 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

Tip:

  • 1 <= task.length <= 104
  • tasks[i]It’s capital English

Answer:

When n===0, there is no interval, so the shortest time is the number of tasks, that is, stasks. Length

If n>0, it is necessary to first find the task that occurs most frequently, arrange it according to the interval, and then insert the interval of other tasks reasonably

You don’t want to try to go through the whole process here, although that would solve the problem, but it’s time-consuming

Here we just need to figure out the following, without actually doing the whole insertion process

Here are three things that can happen

  1. If the number of remaining tasks is more than the number of intervals, it indicates that there must be more types of remaining tasks than the number of intervals. In this case, arrange tasks appropriately, and the shortest time is the number of tasks

    Example:

    tasks = ["A","A","A","A","A","A","B","B","B","B","C","C","C","C","D","E","E","F","F"], N = 2 after an arrangement / / the result of A, B, C, A, B, C, A, B, C, A, B, C, A, E, F, A, E, F, DCopy the code

  2. If the number of remaining tasks is less than the interval, the interval cannot be filled, and the shortest time is the execution time of the task with the most occurrences

    Example:

    The tasks = [" A ", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"], n = 2 / / the result of A arrangement after A, B, C, A, D, E, A, F, G, A, A,,, ACopy the code

  3. It should be noted that there are multiple tasks with the most possible frequency, and the shortest time in this case is equal to the execution time of the task with the most frequency plus the number of tasks with the most frequency -1

    Example:

    [" A ", "A", "A", "B", "B", "B"), n = 2 after an arrangement / / the result of A, B, A, A, B, A, BCopy the code

Therefore, the problem only needs to find the number of tasks that occur the most frequently, and whether there are multiple tasks that occur the most frequently, and find their execution time

Compare with the number of tasks, return the maximum value

The code is as follows:

var leastInterval = function(tasks, n) { const length = tasks.length; If (n===0) return length; Const map = new map (); for(let i = 0; i<tasks.length; i++){ if(map.has(tasks[i])){ map.set(tasks[i],map.get(tasks[i])+1) }else{ map.set(tasks[i],1) } } // Let maxLen = 0,maxLenNum = 0; map.forEach(item => { if(item>maxLen){ maxLen = item; maxLenNum = 1; }else if(item===maxLen){maxLenNum++}}) return math.max ((n+1)*(maxlen-1)+maxLenNum,length) };Copy the code

At this point we are done with leetcode-621- task scheduler

If you have any questions or suggestions, please leave a comment!