leetcode621. task scheduler

LeetCode Series articles

One 、 Title Description

   Here's an array of characters for you $tasks$ It means CPU List of tasks to be performed . Each letter represents a different kind of task . Tasks can be performed in any order , And every task can be in 1 In unit time . At any unit time ,CPU Can complete a task , Or on standby .
 
   However , There must be an integer between two tasks of the same kind $n$ The cooling time of , So at least there's continuity $n$ In units of time CPU On different missions , Or on standby .
 
   You need to calculate the minimum time required to complete all tasks .

Two 、 Example

   Input ： tasks = [‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’], n = 2
   Output ： 8
 
   explain ： A -> B -> ( On standby ) -> A -> B -> ( On standby ) -> A -> B
      In this example , The interval length between two tasks of the same type must be n = 2 The cooling time of , It takes only one unit time to perform a task , So in the middle （ On standby ） state .
 
   Be careful ： Tasks are expressed in capital English letters .

3、 ... and 、 Main idea

   Calculate the minimum time required to complete all tasks according to the task list , First, we need to find the task that needs to be executed the most times in the task list , Then take this task as the timeline for analysis .

   Suppose that the task that needs to be executed the most times in the given task list A, Then we can use a matrix to show the execution of tasks A The timing of the . because CPU There must be at least a length of $n$ The cooling time of , In order to minimize the cooling time , The width of the matrix should be set to $n+1$, And the height of the matrix is the task A The number of executions required .

   If there are only tasks in the task list A, In addition to performing tasks in this matrix A Out of your position , Other positions correspond to “ Standby status ”, And when the last task is finished A when , All tasks have been completed , So what's left in the last row of the matrix $n-1$ At this time, the position is not counted into the time required to complete the task （ In the picture below, we use ╳ Express ）.

   The time required to complete all tasks at this time is ：$(MaxExec-1)\times (n+1)+1$

   If there are other tasks in the task list A There are other kinds of tasks besides , Then these tasks can be added to the diagram “ Standby status ” The location of , If these tasks can all be arranged in “ Standby status ” among , Then the time required to complete all tasks at this time is the same as before .

   Mission A It is the task that needs to be performed the most times , Therefore, there will be no task A More tasks required , But we cannot guarantee that there is no required number of times and tasks A Same task . If this happens , We need to add a position in the last row of the matrix to perform this task .

   therefore , If the required number of executions in the task list is equal to $MaxExec$ The number of tasks is $num$, Then the time required to complete all tasks is ：$(MaxExec-1)\times (n+1)+num$

   Now we are adding other kinds of tasks to the matrix “ Standby status ” The location of , If the number of times the task needs to be performed is the same as $MaxExec$ equal , Then we need to add the corresponding position in the last row of the matrix . But if in the matrix “ Standby status ” All the positions are filled ？ What should I do with the remaining tasks in the task list ？

   At this time, we can expand the width of some rows in the matrix , Then insert the task into these extended locations . Because when the matrix is not expanded , The interval between the same tasks in the matrix is exactly $n$, Now that we are in the matrix “ Standby status ” The position of is filled , Then we can insert the remaining tasks directly after the row of the matrix , After inserting, the task in the original matrix does not violate “ The interval between the same tasks is at least $n$ ” The provisions of the , And the newly inserted task also meets the cooling requirements .

   therefore , If the total number of tasks to be performed in the task list is greater than the size of the matrix we calculated , Then the time required to complete all tasks at this time is the number of tasks in the task list .

Four 、 Code implementation

Although the idea of this topic is complex , But it is still very simple to put this idea into code .

1. Count the number of times each task appears in the task list .（ Because tasks are expressed in capital letters , So just use a size of 26 Of vector Containers for storage ）
2. Sort the tasks according to the number of occurrences from more to less .（ here vector The first of them 0 The first value is $MaxExec$ Value ）
3. Count the number of tasks whose occurrence times are equal to the maximum occurrence times .
4. Compare the calculated value with the total number of tasks to be performed , Returns a larger value .

The code is as follows ：