【Lintcode】945. Task Scheduler

题目地址：

https://www.lintcode.com/problem/task-scheduler/description

给定一系列任务，以大写字母表示，再给定一个冷却时间，每个任务需要花一个单位的时间完成，并且相同任务之间需要 n n n个单位的冷却时间。要求安排这些任务的执行顺序，使得花费的总时间最小。

具体算法参考https://blog.csdn.net/qq_46105170/article/details/109096801。这里给出另一种计算方式。

由算法知道，不妨设出现次数最多的任务是 A A A，最短时间的任务安排方式是 A , . . . , A , . . . , A , . . . A,...,A,...,A,... A,...,A,...,A,...这样，将其余任务尽可能”平均“的放在 A A A的后面。假设 A A A后面已经留了 n − 1 n-1 n−1个idle的位子了，那么从最后一个 A A A向前算，一共有 ( m A − 1 ) ∗ n (m_A-1)*n (mA​−1)∗n个位置已经被安排了。接下来将其余任务依次放到每个 A A A后面，也就是将idle的位置占上。很显然，花费时间变长当且仅当最后一个 A A A后面被安排了任务，也就是说存在某个任务出现次数和 A A A一样多。填完之后，如果发现算出来的耗费时间比任务总数更少，那就说明没有idle，则返回任务总数。代码如下：

public class Solution {
    /**
     * @param tasks: the given char array representing tasks CPU need to do
     * @param n:     the non-negative cooling interval
     * @return: the least number of intervals the CPU will take to finish all the given tasks
     */
    public int leastInterval(char[] tasks, int n) {
        // write your code here
        int[] count = new int[26];
        int max = 0;
        for (int i = 0; i < tasks.length; i++) {
            char task = tasks[i];
            count[task - 'A']++;
            max = Math.max(max, count[task - 'A']);
        }
        
        int res = (max - 1) * (n + 1);
        for (int i = 0; i < count.length; i++) {
            if (count[i] == max) {
                res++;
            }
        }
        
        return Math.max(res, tasks.length);
    }
}

时间复杂度 O ( m ) O(m) O(m)， m m m为任务数，空间 O ( 1 ) O(1) O(1)。