621. 任务调度器

[wengzc]

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

 

示例 ：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 

 

提示：

1. 任务的总个数为 [1, 10000]。

2. n 的取值范围为 [0, 100]。

题目链接：https://leetcode-cn.com/problems/task-scheduler

[wengzc]

思路分析：见题解

解法一：找规律，完成所有任务的最短时间取决于出现次数最多的任务数量

/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function (tasks, n) {
    let len = tasks.length
    let arr = new Array(26).fill(0)
    for (let i = 0; i < len; i++) {
        let index = tasks[i].charCodeAt() - 'A'.charCodeAt()
        arr[index]++
    }
    arr.sort((a, b) => {
        return b - a
    })
    let max = arr[0]
    let res = (max - 1) * (n + 1) + 1
    for (let i = 1; i < 26; i++) {
        if (arr[i] === max) {
            res++
        }
    }
    return res > len ? res : len
};

解法二：排序法，每一轮选择不超过 n + 1 个任务(按任务次数降序选择)执行，直到所有的任务被执行

var leastInterval = function (tasks, n) {
    let len = tasks.length
    let arr = new Array(26).fill(0)
    for (let i = 0; i < len; i++) {
        let index = tasks[i].charCodeAt() - 'A'.charCodeAt()
        arr[index]++
    }
    arr.sort((a, b) => {
        return b - a
    })
    let time = 0
    while (arr[0] !== 0) {
        let i = 0
        while (i <= n) {
            if (arr[0] === 0) {
                break
            }
            if (arr[i] > 0) {
                arr[i]--
            }
            time++
            i++
        }
        arr.sort((a, b) => {
            return b - a
        })
    }
    return time
};