621 Task Cheduler

621-Task Scheduler

题目：Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order.Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

Input: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

The number of tasks is in the range [1, 10000]. The integer n is in the range [0, 100].

Related Topics Array Greedy Queue

很遗憾，这道题没想出来怎么搞。唯一想到的一点就是需要用某个数据结构(例如map)统计数组中每个类型出现的次数，找到出现最多的那个元素，让CPU第一个执行这个任务(这是非常明确的)。后续就没想到怎么办了，查询了网上的答案，发现了一种比较好的思维

方法一：统计空闲槽的个数。总的执行时间就等于任务数 + 所需的空闲槽数目。比如，tasks = [“A”,“A”,“A”,“B”,“B”, “B”,“C”], n = 2。A出现的的次数最多。那么花费时间最少的执行顺序一定是这样的A##A##A，其中#代表你需要在两个A之间插入的其他类别任务或者空闲槽。那么我们就知道了，最多需要的空闲槽数目是n*(最多的次数 - 1)。最多的次数 - 1即是轮数(除最后一轮以外)。

实际上，所需的空闲槽数等于最多需要的减去 其他task 在除去最后一轮以外的轮次中所占用的槽数。来看下面的代码：

public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char task : tasks) {
        count[task - 'A']++;
    }
    Arrays.sort(count);
    int idleCount = n * (count[25] - 1);
    for (int i = count.length - 2; i > 0 && count[i] > 0; i--) {
        //此处求min是因为可能有多个任务的count值同时为最大，需要去除最后一轮
        idleCount -= Math.min(count[25] - 1, count[i]);
    }
    return idleCount > 0 ? idleCount + tasks.length : tasks.length;
}

另一种思路：不用统计空闲槽数目，因为除了最后一轮以外，其余每一轮所需的时间肯定是(n + 1)，那么这些轮所需的总时间数为 (n + 1) * (最多的次数 - 1)。最后一轮只有数量等于最多的次数的那些task才需要被调度，因此只需要统计出数量为最多的次数的 task数目，加上前面的总时间即可。如下代码：

public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char task : tasks) {
        count[task - 'A']++;
    }
    Arrays.sort(count);
    int maxValue = count[25];
    int val = 0;
    for(int i = 25; i >= 0; i--) {
        if(count[i] == count[25]) {
            val++;
        }
    }
    return Math.max(tasks.length, val + (n + 1) * (maxValue - 1));
}

此处值得思考的是，最后一步为什么求的是max。