Array-Task Scheduler

Description:
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 1:

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].

Solution1:

//相当于用数组做了一个优先级队列,注意每次选择n+1个元素(相当于一个环,不足的地方用闲置填充)后,使用了Arrays.sort()排序,元素的个数相当于元素的权重，优先级大的先处理
public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int time = 0;
        while (map[25] > 0) {
            int i = 0;
            while (i <= n) {
                if (map[25] == 0)
                    break;
                if (i < 26 && map[25 - i] > 0)
                    map[25 - i]--;
                time++;
                i++;
            }
            Arrays.sort(map);
        }
        return time;
    }
}

Solution2:

//使用map计数,然后将元素对应的数字放入优先级队列中,注意每轮取出元素有一个List类型的temp保存取出来了元素个数-1,，依次迭代，直到优先级队列为空，即所有元素都放好对应的位置了(还有一个需要注意的地方是,内层的迭代中判断条件为queue.isEmpty() && temp.size() == 0,表示queue中所有元素被取出，且个数为0)
public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        PriorityQueue < Integer > queue = new PriorityQueue < > (26, Collections.reverseOrder());
        for (int f: map) {
            if (f > 0)
                queue.add(f);
        }
        int time = 0;
        while (!queue.isEmpty()) {
            int i = 0;
            List < Integer > temp = new ArrayList < > ();
            while (i <= n) {
                if (!queue.isEmpty()) {
                    if (queue.peek() > 1)
                        temp.add(queue.poll() - 1);
                    else
                        queue.poll();
                }
                time++;
                if (queue.isEmpty() && temp.size() == 0)
                    break;
                i++;
            }
            for (int l: temp)
                queue.add(l);
        }
        return time;
    }
}

Best Solution:

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int max_val = map[25] - 1, idle_slots = max_val * n;
        for (int i = 24; i >= 0 && map[i] > 0; i--) {
            idle_slots -= Math.min(map[i], max_val);
        }
        return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
    }
}

这个算法初看有点难以理解,我们用图形来解释

此算法核心为找出空闲点,那么加上任务个数即为总共耗费的时间。
我们要理解最关键的两点:
1.Figure2为4*5维，不代表只能有5(n+1)列,比如若D个数为3,且还有E*3，F*3，那么是可以扩充到6列的,max_val之前的矩阵在扩充前都是见缝插针，同个元素从上往下插入,如果插满，那么向右扩充
2.Figure2最下面一行只有跟最大出现次数(本例为A)同样次数的元素(本例为B)出现。
那么问题简单了,如果可能idle_slot小于等于0,那么说明max_val之前的矩阵(该矩阵的列可以不断扩充),被填满了,那么总时间即为任务数。如果idle_slot大于0,说明max_val之前的矩阵(该矩阵未扩充)没有被填满，那么总时间即为任务数+闲置数(idle_slots)