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

For example, [“A”,”A”,”A”,”B”,”B”,”B”,”B”,”B”,”B”],”A” might stand for eating,”B” might stand for sleeping,” n “might stand for how often it should be done before it can be done again, when n=2, it should be done every two cycles, Let’s say everything runs in cycle 1, which is 1 and eats dinner A, and the next meal can only be at 3, and in between we can do something else, like B goes to sleep. That becomes eat, sleep, standby, eat, sleep, standby…

So if we think of n as a period, then we can do n plus 1 things in this period. And the number of things we have to do the most, is how many cycles we have to do. When the number of A’s is 3, we need three periods.

We take [” A “, “A”, “A”, “A”, “A”, “A”, “B”, “B”, “B”, “B”, “B”, “B”, “C”, “C”, “D”, “D”, “D”, “F”, “F”], n = 2, for example:

The one that needs to run for the most times is A=6 and the time period is n=2. Then we build A bucket with each layer volume 3 and height 6

Assuming that we have no other tasks, the time we need to execute is (6-1)*3+1=16, because the last layer will be finished after we finish A, and there is no need to wait later.

As we gradually add new tasks to it

When the rest of the task and the greatest number of tasks performed by the number of phase at the same time, we will be on the total mission time + 1, so we want to know how many kinds of task execution times and we recorded the highest number of tasks at the same times, and fewer tasks, such as C task will not take more time, will fill on standby. We just need to record the number of times B is done (6-1) times 3+2=17

The previous two cases are summed up as follows: Total queuing time = (Number of buckets -1) x (n + 1) + number of tasks in the last bucket

What do we do when the cooldown is short and there are many tasks to perform

At this point, we performed D three more times, but still did not exceed the previous standby state, so the total execution time remained the same. But what if the list continues to grow.

We don’t need to add new buckets, because adding new buckets might mean we need more standby, we just need to expand the previous bucket. The insertion minimizes the time required to increase and satisfies the standby state of the added task.

Insert before: ABC from ABC | | ABD | ABD | ABD | AB: after insert ABCF | ABCF | ABD | ABD | ABD | AB

We inserted task F into the first and second buckets, and it was not hard to find that no matter how many more tasks we inserted, we could handle it similarly, and the newly inserted element must satisfy the cooling requirements.

So to sum up:

  • Record the maximum number of tasks N, see how many tasks are tied for the highest number of tasks, that is, the number of tasks X of the last bucket, calculateNUM1=(N-1)*(n+1)+x
  • NUM2=tasks.size()
  • Compare the maximum of the two

If NUM2 is larger, it is the last graph. In the case that the normal time is filled up, the extra tasks can be directly expanded, and the required time is exactly the length of the array, so there is no standby state to fill. A larger NUM1 indicates that there are no buckets to expand and a standby state may exist.

var leastInterval = function (tasks, n) {
  const arr = new Array(26).fill(0);
  const len = tasks.length
  for (let i = 0; i < tasks.length; i++) {
    const char = tasks[i]
    arr[char.charCodeAt() - "A".charCodeAt()]++
  }
  for (let i = 0; i < arr.length;) {
    const num = arr[i];
    if (num == 0) {
      arr.splice(i, 1)
    } else {
      i++
    }
  }
  arr.sort((a, b) => b - a)
  console.log(arr);
  let cnt = 1;
  while (cnt < arr.length && arr[cnt] === arr[0]) {
    cnt++
  }
  return Math.max(len, cnt + (n + 1) * (arr[0] - 1))
};
Copy the code

Complexity analysis

  • Time complexity O(nlogn)
  • Space complexity O(1)