“This is the 24th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

621. Task scheduler

Simulation method

Simulating the process of completing the task in the shortest time;

Here’s a step-by-step explanation:

First, count the number of times each task needs to be executed and put the data in the list.

  let list = Array(26).fill(0)
  for (let i = 0; i < len; i++) {
    const idx = tasks[i].charCodeAt() - 'A'.charCodeAt()
    list[idx] += 1
  }
Copy the code

Step 1: Remove the task whose execution times are 0

list = list.filter((v) = > v > 0)
Copy the code

Step 3: The list length is 0, and all tasks are completed.

while (list.length) {
// Execute tasks, number of unexecuted tasks -1;

// Remove tasks that need to be performed 0 times
 list = list.filter((v) = > v > 0)}Copy the code

Step 4: Discuss tasks by category

When the number of unexecuted tasks is less than the cooling time n; Each task is executed once. The number of times that the corresponding task is not executed -1

When the number of unexecuted tasks is greater than the cooling time n; The task whose subscript is less than n is executed once. Number of times that the corresponding task is not executed -1

Boundary processing

When executing a mission for the last time, there is no need to count the cooldown time into the total time;

Sort the list and loop again until the number of list tasks is zero

 if (l < n) {
      list = list.map((v) = > v - 1)}else {
      list = list.map((v, i) = > (i <= n ? v - 1 : v))
      list.sort((a, b) = > b - a)
    }
Copy the code
var leastInterval = function (tasks, n) {
  const len = tasks.length
  if (n === 0) return len
  let list = Array(26).fill(0)
  for (let i = 0; i < len; i++) {
    const idx = tasks[i].charCodeAt() - 'A'.charCodeAt()
    list[idx] += 1
  }

  list = list.filter((v) = > v > 0)
  let result = 0
  while (list.length) {
    const l = list.length
    if (l < n) {
      list = list.map((v) = > v - 1)}else {
      list = list.map((v, i) = > (i <= n ? v - 1 : v))
      list.sort((a, b) = > b - a)
    }

    list = list.filter((v) = > v > 0)
    if (list.length === 0) {
      return result + l
    }
    result += n + 1
  }
  return result
}
Copy the code

Task barrels

Put tasks in buckets;

Dynamic attitude

Static figure

code

var leastInterval = function (tasks, n) {
  const len = tasks.length
  if (n === 0) return len
  let list = Array(26).fill(0)

  let max = 0
  for (let i = 0; i < len; i++) {
    const idx = tasks[i].charCodeAt() - 'A'.charCodeAt()
    list[idx] += 1
    max = Math.max(max, list[idx])
  }
  list = list.filter((v) = > v > 0)
  const maxNum = list.filter((v) = > v === max)
  const t1 = (max - 1) * (n + 1) + maxNum.length
  return Math.max(len, t1)
}
Copy the code