Subject to introduce

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

Enter: tasks = ["A"."A"."A"."B"."B"."B"], n = 2Output:8Explanation: A -> B -> (Standby) -> A -> B -> (Standby) -> A -> B In this example, the interval length between two tasks of the same type must be N =2While it only takes one unit of time to perform a task, there is a state in between.Copy the code

Example 2

Enter: tasks = ["A"."A"."A"."B"."B"."B"], n = 0Output:6Explanation: In this case, any size is6All of these permutations will work, because n is equal to0
["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

Enter: tasks = ["A"."A"."A"."A"."A"."A"."B"."C"."D"."E"."F"."G"], n = 2Output:16Explanation: 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
• nThe value range of is[0, 100]

Leetcode -621 Mission Scheduler station B video

Their thinking

This problem should start with one type of task and then consider more types of task

1. Suppose there is only one task, the number of tasks is 5, and the cooldown time is n = 2. We perform the task sequentially, and two cooldowns are required between each two tasks, then we can get the following “box”.

In this case, the task completion time should be:(Quests -1) * (Cooldown + 1) + 1

2. Assuming that there are two kinds of tasks, the number of tasks of A is 5, the number of tasks of B is 3, and the cooling time is n = 2, the following model can be obtained

At this time, the task completion time is still:(Maximum number of tasks - 1) * (Cooldown + 1) + 1

3. Assuming that there are two kinds of tasks, the number of tasks of A is 5, the number of tasks of B is also 5, and the cooling time is n = 2, the following model can be obtained

In this case, the task completion time is:(Maximum number of quests - 1) * (Cooldown + 1) + maximum number of quests

4. Assuming tasks: A = 5, B = 5, C = 2, D = 2, cooldown n = 2, then all tasks just fill the “box” above, so the time to complete tasks is: (Maximum number of quests – 1) * (Cooldown + 1) + maximum number of quests or all quests

5. If a new task is added on the basis of 4, then the position of the task is critical. If we put it down, there will be extra cooldown time

So the key here is to figure out(Maximum number of quests - 1) * (Cooldown + 1) + maximum number of quests 和 Number of tasksThe larger value

The problem solving code

var leastInterval = function(tasks, n) {
    const obj = {}
    for (let i = 0; i < tasks.length; i++) {
        if(! obj[tasks[i]]) { obj[tasks[i]] =1
        } else {
            obj[tasks[i]]++
        }
    }
    // Get the number of tasks of the largest task type
    const max = Math.max(... Object.values(obj))let maxCount = 0
    // Get the maximum number of tasks
    Object.values(obj).forEach(i= > {
        if (i === max) maxCount++
    })
    // Get the larger value between the two
    return Math.max((max - 1) * (n + 1) + maxCount, tasks.length)
};
Copy the code

So that’s the answer to this question, Welcome to see my other article [luffy]_ ring list [Luffy]_ happy number [Luffy]_ reverse list [Luffy]_ reverse list [Luffy]_K group of flipped list [Luffy]_ rotation list [Luffy]_ pairwise swap list of nodes [Luffy]_ recent requests [Luffy]_ KTH number [Luffy]_ Intimate string [Luffy]_ lemonade change [Luffy]_ Pancakes sort