Record an algorithm problem

Task scheduler

621. Task Scheduler – LeetCode (leetcode-cn.com)

Requirements:

1. Each task takes one unit of time. 2. Find the shortest timeCopy the code

So let’s do some simulation. Explore the process, the following will provide two solutions, one is a violent solution, one is the use of the law.

  • [“A”,”A”,”A”,”B”,”B”,”B”,”C”,”C”], n = 2

    A -> B -> C -> A -> B -> C -> A -> B, with at least two tasks between A and the next A.Copy the code

  • If it is [“A”,”A”,”A”,”B”,”B”,”B”], n = 2

    The execution sequence is A -> B -> Empty -> A -> B -> empty -> A -> BCopy the code

  • If it is [” A “, “A”, “A”, “B”, “B”, “B”, “C”, “C”, “D”, “E”], n = 2

    Execution sequence is A - > B > C - A - > B > D - > - > - > E - A - > B > CCopy the code

It’s basically going from high to low.

So let’s do the number first

    function leastInterval(tasks, n) {
        const countObj = tasks.reduce((total, curr) = > {
            if (total[curr]) {
                total[curr]++
            } else {
                total[curr] = 1}}, {})// Select * from (*)
        const arr = Object.values(countObj).sort((a, b) = > b - a)
    }
Copy the code

Assumption is that [” A “, “A”, “A”, “B”, “B”, “B”, “C”, “C”), n = 2, all species at this time has get to the number of array (3, 3, 2), then observe the relationship between n and number. The transformation into a stereogram is as follows;

     A B
     A B C
     A B C
Copy the code

We’ll see that the period of the task is n + 1, so this is 3 periods. You can then write a loop to process it.

    // arr = [3, 3, 2]
    let count = 0
    for(let i = 0; i < n + 1; n++) {
        arr[i]--
        count++
    }
Copy the code

This completes the first three tasks in the array, but we also need to consider the last A -> B, only two tasks, so the loop needs to be conditional. You need a value to count. (Pay attention to detail, count first and then subtract)

    // arr = [1, 1, 0]
    let count = 0
    for(let i = 0; i < n + 1; n++) {
        if (arr[i]) {
            count++
        }
        arr[i]--
    }
Copy the code

As the variety grows, we need to make it sequential. [3, 2, 1, 1, 1], n = 2, it is obvious that we need to wrap another layer with a loop, what are the termination conditions of the loop?

    let count = 0
    while(?) {
        for(let i = 0; i < n + 1; n++) {
            if (arr[i]) {
                count++
            }
            arr[i]--
        }
    }
Copy the code
Tasks A, B, A, B, A, A, and C are spaced, and the interval is if you don't do any other tasks, you have to wait for at least the highest number of A's to finish. The mission is over. So when the degree of A is zero, it stops. And because you're dealing with the first three at a time, you need to reorder them at the end of each cycle. Because it's a brute force solution, I don't care about performance. But there is a little pit, [1, 0, 0], where we see that arR is only evaluated once, actually three times, and we can't use arr[0] because arR is only evaluated once for [1,1,0].Copy the code
    let count = 0
    while(arr[0]) {
        for(let i = 0; i < n + 1; n++) {
            if (arr.filter(_= > _ > 0).length) {
                count++
            }
            arr[i]--
        }
        
        arr = arr.sort((a, b) = > b - a)
    }
Copy the code

And then the number is collected. The complete code for the violent solution is as follows

   function leastInterval(tasks, n) {
       const obj = tasks.reduce((total, curr) = > {
         if (total[curr]) {
           total[curr]++
         } else {
           total[curr] = 1
         }

         return total
       }, {})

       let arr = Object.values(obj).sort((a, b) = > b - a)
       // Get the maximum number of times
       const max = arr[0]
       // The following n is n+1, so this is reassigned
       n = n + 1
       
       // The length must be greater than or equal to n
       // Manually populate waiting tasks
       if (arr.length < n) {
         while(arr.length ! == n) { arr.push(max -1)}}let count = 0
       while (arr[0]) {
         for (let i = 0; i < n; i++) {
           if (arr.filter(_= > _ > 0).length) {
             count++
           }

           arr[i]--
         }

         arr = arr.sort((a, b) = > b - a)
       }

       return count
     }
Copy the code

In fact, the rule has basically come out.

  1. When there is a waiting task, execute at least (Max – 1) * n times, then add the maximum number of times

    A B A B C A B C can be divided into A B ----- there are certain numbers A B C A B CCopy the code

  2. Of course, there may be no waiting task, and we’ll fill it with other tasks

    A A B A B C D E E ----Copy the code

  3. It might be more than n plus 1

    A, E, F, A, B, D, H, A, B, C, G in this case, tasks don't have to wait, they can be separated by n+1 or more tasks that are exactly equal to the total number of tasks. tasks.lengthCopy the code

So it’s (max-1) * n + maxCount or the total number of tasks (maxCount is the number of tasks equal to Max)

The former will miss some of the redundant tasks after filling, so the maximum of the two is returned as the result. The complete code is as follows:

    function leastInterval(tasks, n) {
        const obj = tasks.reduce((total, curr) = > {
          if (total[curr]) {
            total[curr]++
          } else {
            total[curr] = 1
          }

          return total
        }, {})

        const arr = Object.values(obj).sort((a, b) = > b - a)

        const max = arr[0]
        n = n + 1
        
        // The top is the same, the bottom is much simpler than the brute force solution.
        let maxCount = 0
        for (; maxCount < n; maxCount++) {
          if(arr[maxCount] ! == max) {break}}return Math.max((max - 1) * n + maxCount, tasks.length)
      }
Copy the code

The end of the