LeetCode 621 - Task Scheduler

Related:
LeetCode 358 - Rearrange String k Distance Apart
LeetCode 767 - Reorganize String
LeetCode 621 - Task Scheduler
https://leetcode.com/problems/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 1:

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

Note:

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

X.https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/621_Task_Scheduler.java

    public int leastInterval(char[] tasks, int n) {
        char[] cnt = new char[26];
        int maxn = 0;
        for (int task : tasks) {
            cnt[task - 'A'] ++;
            maxn = Math.max(maxn, cnt[task - 'A']);
        }
        int ans = (maxn - 1) * (n + 1);
        for (int i = 0; i < 26; i ++)
            if (cnt[i] == maxn)
                ans ++;
        return Math.max(ans, tasks.length);
    }

Time complexity : $O(n)$. We iterate over $tasks$ array only once. ($O(n)$).Sorting $tasks$ array of length $n$ takes $O\big(26log(26)\big)= O(1)$ time. After this, only one iteration over 26 elements of $map$ is done($O(1)$.

https://blog.csdn.net/TheSnowBoy_2/article/details/73556561
解法1：【贪心 + 数学表达】

• 【贪心算法】角度的选择很重要。作者在这里采取了分块的形式，按照出现频率最多（假设频率为k）的将其分为了k块，然后每一轮向这k个区间个插入1个。如何选择贪心策略？
• 【数学公式表达】通过数学公式明确考虑问题的角度，清晰表达解答问题的思路，明确其中涉及的变量以及变量函数间的关系。
• 【证明贪心有效性】如何证明一个贪心策略是能够解决一个问题的？

http://www.cnblogs.com/grandyang/p/7098764.html

这道题让我们安排CPU的任务，规定在两个相同任务之间至少隔n个时间点。说实话，刚开始博主并没有完全理解题目的意思，后来看了大神们的解法才悟出个道理来。下面这种解法参考了大神fatalme的帖子，由于题目中规定了两个相同任务之间至少隔n个时间点，那么我们首先应该处理的出现次数最多的那个任务，先确定好这些高频任务，然后再来安排那些低频任务。如果任务F的出现频率最高，为k次，那么我们用n个空位将每两个F分隔开，然后我们按顺序加入其他低频的任务，来看一个例子：

AAAABBBEEFFGG 3

我们发现任务A出现了4次，频率最高，于是我们在每个A中间加入三个空位，如下：

A---A---A---A

AB--AB--AB--A   (加入B)

ABE-ABE-AB--A   (加入E)

ABEFABE-ABF-A   (加入F，每次尽可能填满或者是均匀填充)

ABEFABEGABFGA   (加入G)

再来看一个例子：

ACCCEEE 2

我们发现任务C和E都出现了三次，那么我们就将CE看作一个整体，在中间加入一个位置即可：

CE-CE-CE

CEACE-CE   (加入A)

注意最后面那个idle不能省略，不然就不满足相同两个任务之间要隔2个时间点了。

这道题好在没有让我们输出任务安排结果，而只是问所需的时间总长，那么我们就想个方法来快速计算出所需时间总长即可。我们仔细观察上面两个例子可以发现，都分成了(mx - 1)块，再加上最后面的字母，其中mx为最大出现次数。比如例子1中，A出现了4次，所以有A---模块出现了3次，再加上最后的A，每个模块的长度为4。例子2中，CE-出现了2次，再加上最后的CE，每个模块长度为3。我们可以发现，模块的次数为任务最大次数减1，模块的长度为n+1，最后加上的字母个数为出现次数最多的任务，可能有多个并列。这样三个部分都搞清楚了，写起来就不难了，我们统计每个大写字母出现的次数，然后排序，这样出现次数最多的字母就到了末尾，然后我们向前遍历，找出出现次数一样多的任务个数，就可以迅速求出总时间长了，下面这段代码可能最不好理解的可能就是最后一句了，那么我们特别来讲解一下。先看括号中的第二部分，前面分析说了mx是出现的最大次数，mx-1是可以分为的块数，n+1是每块中的个数，而后面的 25-i 是还需要补全的个数，用之前的例子来说明：

AAAABBBEEFFGG 3

A出现了4次，最多，mx=4，那么可以分为mx-1=3块，如下：

A---A---A---

每块有n+1=4个，最后还要加上末尾的一个A，也就是25-24=1个任务，最终结果为13：

ABEFABEGABFGA

再来看另一个例子：

ACCCEEE 2

C和E都出现了3次，最多，mx=3，那么可以分为mx-1=2块，如下：

CE-CE-

每块有n+1=3个，最后还要加上末尾的一个CE，也就是25-23=2个任务，最终结果为8：

CEACE-CE

好，那么此时你可能会有疑问，为啥还要跟原任务个数len相比，取较大值呢？我们再来看一个例子：

AAABBB 0

A和B都出现了3次，最多，mx=3，那么可以分为mx-1=2块，如下：

ABAB

每块有n+1=1个？你会发现有问题，这里明明每块有两个啊，为啥这里算出来n+1=1呢，因为给的n=0，这有没有矛盾呢，没有！因为n表示相同的任务间需要间隔的个数，那么既然这里为0了，说明相同的任务可以放在一起，这里就没有任何限制了，我们只需要执行完所有的任务就可以了，所以我们最终的返回结果一定不能小于任务的总个数len的，这就是要对比取较大值的原因了。

https://leetcode.com/articles/task-scheduler/
https://leetcode.com/problems/task-scheduler/discuss/104496/concise-java-solution-on-time-o26-space
Approach #3 Calculating Idle slots
First consider the most frequent characters, we can determine their relative positions first and use them as a frame to insert the remaining less frequent characters. Here is a proof by construction:

Let F be the set of most frequent chars with frequency k.
We can create k chunks, each chunk is identical and is a string consists of chars in F in a specific fixed order.
Let the heads of these chunks to be H_i; then H_2 should be at least n chars away from H_1, and so on so forth; then we insert the less frequent chars into the gaps between these chunks sequentially one by one ordered by frequency in a decreasing order and try to fill the k-1 gaps as full or evenly as possible each time you insert a character. In summary, append the less frequent characters to the end of each chunk of the first k-1 chunks sequentially and round and round, then join the chunks and keep their heads' relative distance from each other to be at least n.

Examples:

AAAABBBEEFFGG 3

here X represents a space gap:

Frame: "AXXXAXXXAXXXA"
insert 'B': "ABXXABXXABXXA" <--- 'B' has higher frequency than the other characters, insert it first.
insert 'E': "ABEXABEXABXXA"
insert 'F': "ABEFABEXABFXA" <--- each time try to fill the k-1 gaps as full or evenly as possible.
insert 'G': "ABEFABEGABFGA"

AACCCBEEE 2

3 identical chunks "CE", "CE CE CE" <-- this is a frame
insert 'A' among the gaps of chunks since it has higher frequency than 'B' ---> "CEACEACE"
insert 'B' ---> "CEABCEACE" <----- result is tasks.length;

AACCCDDEEE 3

3 identical chunks "CE", "CE CE CE" <--- this is a frame.
Begin to insert 'A'->"CEA CEA CE"
Begin to insert 'B'->"CEABCEABCE" <---- result is tasks.length;

ACCCEEE 2

3 identical chunks "CE", "CE CE CE" <-- this is a frame
Begin to insert 'A' --> "CEACE CE" <-- result is (c[25] - 1) * (n + 1) + 25 -i = 2 * 3 + 2 = 8

for the last line (c[25] - 1) * (n + 1) + 25 - i):

c[25]-1: the most frequent letter happen time minus 1
*(n+1): count for the loops for above
+25-i: count for the less frequence letters.

For example:
tasks = ['A','A','A','B','B','B'], n = 2

most frequent letter : A (happen 3 times, let it minus 1= 2)
count loops: (n+1) =3
plus the letters left: A,B.
[A -> B -> idle]*loop1* -> [A -> B -> idle]*loop2* -> A -> B.

// (c[25] - 1) * (n + 1) + 25 - i  is frame size
// when inserting chars, the frame might be "burst", then tasks.length takes precedence
// when 25 - i > n, the frame is already full at construction, the following is still valid.
    public int leastInterval(char[] tasks, int n) {

        int[] c = new int[26];
        for(char t : tasks){
            c[t - 'A']++;
        }
        Arrays.sort(c);
        int i = 25;
        while(i >= 0 && c[i] == c[25]) i--;

        return Math.max(tasks.length, (c[25] - 1) * (n + 1) + 25 - i);
    }

If we are able to, somehow, determine the number of idle slots($idle\_slots$), we can find out the time required to execute all the tasks as $idle\_slots + Total Number Of Tasks$. Thus, the idea is to find out the idle time first.

Time complexity : $O(n)$. We iterate over $tasks$ array only once. ($O(n)$).Sorting $tasks$ array of length $n$ takes $O\big(26log(26)\big)= O(1)$ time. After this, only one iteration over 26 elements of $map$ is done($O(1)$.

    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;
    }

X.  Best

优点是代码更容易读懂，而且变量命名很reasonable，前半部分都是一样的，求出最多的次数mx，还有同时出现mx次的不同任务的个数mxCnt。这个解法的思想是先算出所有空出来的位置，然后计算出所有需要填入的task的个数，如果超出了空位的个数，就需要最后再补上相应的个数。注意这里如果有多个任务出现次数相同，那么将其整体放一起，就像上面的第二个例子中的CE一样，那么此时每个part中的空位个数就是n - (mxCnt - 1)，那么空位的总数就是part的总数乘以每个part中空位的个数了，那么我们此时除去已经放入part中的，还剩下的task的个数就是task的总个数减去mx * mxCnt，然后此时和之前求出的空位数相比较，如果空位数要大于剩余的task数，那么则说明还需补充多余的空位，否则就直接返回task的总数即可

https://leetcode.com/problems/task-scheduler/discuss/104500/java-on-time-o1-space-1-pass-no-sorting-solution-with-detailed-explanation

The key is to find out how many idles do we need.
Let's first look at how to arrange them. it's not hard to figure out that we can do a "greedy arrangement": always arrange task with most frequency first.
E.g. we have following tasks : 3 A, 2 B, 1 C. and we have n = 2. According to what we have above, we should first arrange A, and then B and C. Imagine there are "slots" and we need to arrange tasks by putting them into "slots". Then A should be put into slot 0, 3, 6 since we need to have at least n = 2 other tasks between two A. After A put into slots, it looks like this:

A ? ? A ? ? A
"?" is "empty" slots.

Now we can use the same way to arrange B and C. The finished schedule should look like this:

A B C A B # A
"#" is idle

Now we have a way to arrange tasks. But the problem only asks for number of CPU intervals, so we don't need actually arrange them. Instead we only need to get the total idles we need and the answer to problem is just number of idles + number of tasks.
Same example: 3 A, 2 B, 1 C, n = 2. After arranging A, we have:
A ? ? A ? ? A
We can see that A separated slots into (count(A) - 1) = 2 parts, each part has length n. With the fact that A is the task with most frequency, it should need more idles than any other tasks. In this case if we can get how many idles we need to arrange A, we will also get number of idles needed to arrange all tasks. Calculating this is not hard, we first get number of parts separated by A: partCount = count(A) - 1; then we can know number of empty slots: emptySlots = partCount * n; we can also get how many tasks we have to put into those slots: availableTasks = tasks.length - count(A). Now if we have emptySlots > availableTasks which means we have not enough tasks available to fill all empty slots, we must fill them with idles. Thus we have idles = max(0, emptySlots - availableTasks);
Almost done. One special case: what if there are more than one task with most frequency? OK, let's look at another example: 3 A 3 B 2 C 1 D, n = 3
Similarly we arrange A first:
A ? ? ? A ? ? ? A
Now it's time to arrange B, we find that we have to arrange B like this:
A B ? ? A B ? ? A B
we need to put every B right after each A. Let's look at this in another way, think of sequence "A B" as a special task "X", then we got:
X ? ? X ? ? X
Comparing to what we have after arranging A:
A ? ? ? A ? ? ? A
The only changes are length of each parts (from 3 to 2) and available tasks. By this we can get more general equations:
partCount = count(A) - 1
emptySlots = partCount * (n - (count of tasks with most frequency - 1))
availableTasks = tasks.length - count(A) * count of tasks with most frenquency
idles = max(0, emptySlots - availableTasks)
result = tasks.length + idles

What if we have more than n tasks with most frequency and we got emptySlot negative? Like 3A, 3B, 3C, 3D, 3E, n = 2. In this case seems like we can't put all B C S inside slots since we only have n = 2.
Well partCount is actually the "minimum" length of each part required for arranging A. You can always make the length of part longer.
E.g. 3A, 3B, 3C, 3D, 2E, n = 2.
You can always first arrange A, B, C, D as:
A B C D | A B C D | A B C D
in this case you have already met the "minimum" length requirement for each part (n = 2), you can always put more tasks in each part if you like:
e.g.
A B C D E | A B C D E | A B C D

emptySlots < 0 means you have already got enough tasks to fill in each part to make arranged tasks valid. But as I said you can always put more tasks in each part once you met the "minimum" requirement.

To get count(A) and count of tasks with most frequency, we need to go through inputs and calculate counts for each distinct char. This is O(n) time and O(26) space since we only handle upper case letters.
All other operations are O(1) time O(1) space which give us total time complexity of O(n) and space O(1)

    public int leastInterval(char[] tasks, int n) {
        int[] counter = new int[26];
        int max = 0;
        int maxCount = 0;
        for(char task : tasks) {
            counter[task - 'A']++;
            if(max == counter[task - 'A']) {
                maxCount++;
            }
            else if(max < counter[task - 'A']) {
                max = counter[task - 'A'];
                maxCount = 1;
            }
        }
        
        int partCount = max - 1;
        int partLength = n - (maxCount - 1);
        int emptySlots = partCount * partLength;
        int availableTasks = tasks.length - max * maxCount;
        int idles = Math.max(0, emptySlots - availableTasks);
        
        return tasks.length + idles;
    }

X. PriorityQueue

Sorting takes O(1) because length of the array is fixed. The loops take O(intervals). So the overall time complexity is O(intervals).

下面这种解法是参考的大神alexander的解法，思路是建立一个优先队列，然后把统计好的个数都存入优先队列中，那么大的次数会在队列的前面。这题还是要分块，每块能装n+1个任务，装任务是从优先队列中取，每个任务取一个，装到一个临时数组中，然后遍历取出的任务，对于每个任务，将其哈希表映射的次数减1，如果减1后，次数仍大于0，则将此任务次数再次排入队列中，遍历完后如果队列不为空，说明该块全部被填满，则结果加上n+1。我们之前在队列中取任务是用个变量cnt来记录取出任务的个数，我们想取出n+1个，如果队列中任务数少于n+1个，那就用cnt来记录真实取出的个数，当队列为空时，就加上cnt的个数
https://leetcode.com/problems/task-scheduler/discuss/104493/c-java-clean-code-priority-queue

0. To work on the same task again, CPU has to wait for time n, therefore we can think of as if there is a cycle, of time n+1, regardless whether you schedule some other task in the cycle or not.

1. To avoid leave the CPU with limited choice of tasks and having to sit there cooling down frequently at the end, it is critical the keep the diversity of the task pool for as long as possible.
2. In order to do that, we should try to schedule the CPU to always try round robin between the most popular tasks at any time.

As @milu point out, we don't really need to store <task - count> pair in the priority_queue, we don't need to know the task name, store counts works good enough:

    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> counts = new HashMap<Character, Integer>();
        for (char t : tasks) {
            counts.put(t, counts.getOrDefault(t, 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        pq.addAll(counts.values());

        int alltime = 0;
        int cycle = n + 1;
        while (!pq.isEmpty()) {
            int worktime = 0;
            List<Integer> tmp = new ArrayList<Integer>();
            for (int i = 0; i < cycle; i++) {
                if (!pq.isEmpty()) {
                    tmp.add(pq.poll());
                    worktime++;
                }
            }
            for (int cnt : tmp) {
                if (--cnt > 0) {
                    pq.offer(cnt);
                }
            }
            alltime += !pq.isEmpty() ? cycle : worktime;
        }
        
        return alltime;
    }




Approach #2 Using Priority-Queue

we can also make use of a Max-Heap($queue$) to pick the order in which the tasks need to be executed. But we need to ensure that the heapification occurs only after the intervals of cooling time, $n$, as done in the last approach.

To do so, firstly, we put only those elements from $map$ into the $queue$ which have non-zero number of instances. Then, we start picking up the largest task from the $queue$ for current execution. (Again, at every instant, we update the current $time$ as well.) We pop this element from the $queue$. We also decrement its pending number of instances and if any more instances of the current task are pending, we store them(count) in a temporary $temp$ list, to be added later on back into the $queue$. We keep on doing so, till a cycle of cooling time has been finished. After every such cycle, we add the generated $temp$list back to the $queue$ for considering the most critical task again.

We keep on doing so till the $queue$(and $temp$) become totally empty. At this instant, the current value of $time$ gives the required result.

• Time complexity : $O(n)$. Number of iterations will be equal to resultant time $time$.
• Space complexity : $O(1)$. $queue$ and $temp$ size will not exceed O(26).

    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;
    }

https://discuss.leetcode.com/topic/92873/c-java-clean-code-priority-queue

0. To work on the same task again, CPU has to wait for time n, therefore we can think of as if there is a cycle, of time n+1, regardless whether you schedule some other task in the cycle or not.
1. To avoid leave the CPU with limited choice of tasks and having to sit there cooling down frequently at the end, it is critical the keep the diversity of the task pool for as long as possible.
2. In order to do that, we should try to schedule the CPU to always try round robin between the most popular tasks at any time.

https://discuss.leetcode.com/topic/92866/java-priorityqueue-solution-similar-problem-rearrange-string-k-distance-apart

The idea used here is similar to - https://leetcode.com/problems/rearrange-string-k-distance-apart
We need to arrange the characters in string such that each same character is K distance apart, where distance in this problems is time b/w two similar task execution.

Idea is to add them to a priority Q and sort based on the highest frequency.
And pick the task in each round of 'n' with highest frequency. As you pick the task, decrease the frequency, and put them back after the round.

public int leastInterval(char[] tasks, int n) {
     Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < tasks.length; i++) {
        map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1); // map key is TaskName, and value is number of times to be executed.
    }
    PriorityQueue<Map.Entry<Character, Integer>> q = new PriorityQueue<>( //frequency sort
            (a,b) -> a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey() - b.getKey());

    q.addAll(map.entrySet());

    int count = 0;
    while (!q.isEmpty()) {
        int k = n + 1;//\\
        List<Map.Entry> tempList = new ArrayList<>();
        while (k > 0 && !q.isEmpty()) {
            Map.Entry<Character, Integer> top = q.poll(); // most frequency task
            top.setValue(top.getValue() - 1); // decrease frequency, meaning it got executed
            tempList.add(top); // collect task to add back to queue
            k--;
            count++; //successfully executed task
        }

        for (Map.Entry<Character, Integer> e : tempList) {
            if (e.getValue() > 0) q.add(e); // add valid tasks 
        }

        if (q.isEmpty()) break;
        count = count + k; // if k > 0, then it means we need to be idle
    }
    return count;
}

https://discuss.leetcode.com/topic/92968/java-greedy-algorithm-with-correctness-proof-using-priorityqueue-and-waiting-list

The idea of greedy algorithm is at each time point we choose the task with most amount to be done and is also at least n apart from the last execution of the same task. Below is a proof of the correctness:

At some time, task A has the most remaining amount to be done and A is also at least n apart from its most recent execution. However, suppose the optimal solution doesn't choose A as the first task but rather chooses B. Assume we have x task A remain and y task B remain, we know x >= y.
Also assume in the optimal solution those m task A are done at a series of time points of a1, a2 ... ax, and n task B are done at a series of time points of b1, b2 ... by and we know that b1 < a1.
Further, we assume k is the largest number that for all i <= k, bi < ai. Now if we swap a1 and b1, a2 and b2 ... ak and bk, it will still be a valid solution since the separation between ak and ak+1 (if exists) becomes even larger. As to bk, it's the previous ak and bk+1 > ak+1 > ak(prev) + n = bk(now) + n.

So we proved that no solution will better than schedule A first.

https://discuss.leetcode.com/topic/92881/java-solution-priorityqueue-and-hashmap

1. Greedy - It's obvious that we should always process the task which has largest amount left.
2. Put tasks (only their counts are enough, we don't care they are 'A' or 'B') in a PriorityQueue in descending order.
3. Start to process tasks from front of the queue. If amount left > 0, put it into a coolDown HashMap
4. If there's task which cool-down expired, put it into the queue and wait to be processed.
5. Repeat step 3, 4 till there is no task left.

    public int leastInterval(char[] tasks, int n) {
        if (n == 0) return tasks.length;
        
        Map<Character, Integer> taskToCount = new HashMap<>();
        for (char c : tasks) {
            taskToCount.put(c, taskToCount.getOrDefault(c, 0) + 1);
        }
        
        Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);
        for (char c : taskToCount.keySet()) queue.offer(taskToCount.get(c));
        
        Map<Integer, Integer> coolDown = new HashMap<>();
        int currTime = 0;
        while (!queue.isEmpty() || !coolDown.isEmpty()) {
            if (coolDown.containsKey(currTime - n - 1)) {
                queue.offer(coolDown.remove(currTime - n - 1));
            }
            if (!queue.isEmpty()) {
                int left = queue.poll() - 1;
         if (left != 0) coolDown.put(currTime, left);
            }
            currTime++;
        }
        
        return currTime;
    }

Approach #1 Using Sorting

The first solution that comes to the mind is to consider the tasks to be executed in the descending order of their number of instances. For every task executed, we can keep a track of the time at which this task was executed in order to consider the impact of cooling time in the future. We can execute all the tasks in the descending order of their number of instances and can keep on updating the number of instances pending for each task as well. After one cycle of the task list is executed, we can again start with the first task(largest count of instances) and keep on continuing the process by inserting idle cycles wherever appropriate by considering the last execution time of the task and the cooling time as well.

But, there is a flaw in the above idea. Consider the case, where say the number of instances of tasks A, B, C, D, E are 6, 1, 1, 1, 1 respectively with n=2(cooling time). If we go by the above method, firstly we give 1 round to each A, B, C, D and E. Now, only 5 instances of A are pending, but each instance will take 3 time units to complete because of cooling time. But a better way to schedule the tasks will be this: A, B, C, A, D, E, ... . In this way, by giving turn to the task A as soon as its cooling time is over, we can save a good number of clock cycles.

From the above example, we are clear with one idea. It is that, the tasks with the currently maximum number of outstanding (pending)instances will contribute to a large number of idle cycles in the future, if not executed with appropriate interleavings with the other tasks. Thus, we need to re-execute such a task as soon as its cooling time is finished.

Thus, based on the above ideas, firstly, we obtain a count of the number of instances of each task in $map$ array. Then, we start executing the tasks in the order of descending number of their initial instances. As soon as we execute the first task, we start its cooling timer as well($i$). For every task executed, we update the pending number of instances of the current task. We update the current time, $time$, at every instant as well. Now, as soon as the timer, $i$'s value exceeds the cooling time, as discussed above, we again need to consider the task with the largest number of pending instances. Thus, we again sort the $tasks$ array with updated counts of instances and again pick up the tasks in the descending order of their number of instances.

Now, the task picked up first after the sorting, will either be the first task picked up in the last iteration(which will now be picked after its cooling time has been finished) or the task picked will be the one which lies at $(n+1)^{th}$ position in the previous descending $tasks$ array. In either of the cases, the cooling time won't cause any conflicts(it has been considered implicitly). Further, the task most critical currently will always be picked up which was the main requirement.

We stop this process, when the pending instances of all the tasks have been reduced to 0. At this moment, $time$ gives the required result.

Time complexity : $O(time)$. Number of iterations will be equal to resultant time $time$.

    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;
    }

X.

// PriorityQueue or Sort, output solution
    private class Task {
        char name;
        int cnt;
        public Task(char name) {
            this.name = name;
            this.cnt = 0;
        }
    }
    
    public int leastInterval(char[] tasks, int n) {
        Task[] tks = new Task[26];
        for (char ch = 'A'; ch <= 'Z'; ch ++)
            tks[ch - 'A'] = new Task(ch);
        for (char task : tasks)
            tks[task - 'A'].cnt ++;
        
        PriorityQueue<Task> pq = new PriorityQueue<Task>(new Comparator<Task>() {
            public int compare(Task a, Task b) {
                return b.cnt - a.cnt;
            } 
        });
        for (int i = 0; i < 26; i ++)
            if (tks[i].cnt > 0)
                pq.add(tks[i]);
        
        int ans = 0;
        List<Character> path = new ArrayList<Character>();
        while (!pq.isEmpty()) {
            List<Task> tmp = new ArrayList<Task>();
            for (int i = 0; i <= n; i ++) {
                ans ++;
                if (!pq.isEmpty()) {
                    Task cur = pq.poll();
                    path.add(cur.name);
                    if (-- cur.cnt > 0) tmp.add(cur);
                    if (pq.isEmpty() && tmp.isEmpty()) break;
                }
            }
            for (Task cur : tmp) pq.add(cur);
        }
        
        for (char cur : path)
            System.out.print(cur + " ");
        System.out.println();
        return ans;
    }

3. 变种 HashMap

(code)

4. FollowUp Queue

or HashMap or Queue+HashMap

1. 输出⽅方案

2. ⾯面试的题⽬目中，执⾏行行task的顺序是给定的，cooling down time只存在于

相同种类 task之间，不不同种类之间不不存在cooling down time。

例例⼦子:[1,1,2,3,1,3,4] cooling down time = 2

output: 1 _ _ 1 2 3 1 _ 3 4

3. 问了了task种类数量量 >> cooldown 和 cooldown >> task的种类数量量 两种

不不同情况下的空间最优的做法，分别写了了实现。

新鲜脸家电面

题目：和利口陆饵要背景类似，但是参数tasks的类型是vector<string>，也就是说每个task都有一个任意长度的名字（可以为空），然后给定所有的task的顺序和cooldown，求完成这个顺序需要的时间。举例：
ABAABC cooldown = 3
AB--A---ABC 答案= 11
. check 1point3acres for more.
问了当task的种类数量<<cooldown的最大值 和 cooldown可以非常大，task的种类数量很少 两种不同情况下的空间最优的做法，分别写了实现

更正：是task的种类数量 >> cooldown的最大值 和 cooldown >> task的种类两种情况

当task种类远大于cooldown时，为什么要用队列呢？仍然需要用Map来记录task出现的位置，怎么减小空间复杂度呢，还是O(n)啊

public int taskScheduler( List<String> tasks, int n) {

        if (tasks == null || tasks.length() == 0) {

            return 0;

        }

        if (n == 0) {

            return tasks.length();

        }

        Map<String, Integer> map = new HashMap<>();

        int time = 0;

        for (String task : tasks) {

            if (map.containsKey(task)) {

                int lastTime = map.get(task);

                time = Math.max(lastTime + n + 1, time + 1);  // choose the bigger one

            } else {

                time = time + 1;

            }

            map.put(task, time);  // last time this task ID has appeard

        }

        return time;

    }

写错了 第一种确实是task种类远大于cooldown。当cooldown较大时我和你的做法是一样的，cooldown较小的话就维护一个队列，记录一个cooldown内做过的任务的时间，然后动态删除已经过期的任务。这样时间复杂度可能会增加到O(kn)，cooldown长度*task个数，但空间复杂度能够降低

task scheduler 经典变种题，正常的维护顺序用map吧，冷却时间很小就用Queue来存任务

我猜你这个做法可以改成只用map存一个cooldown size，每次time处理完之后扫一遍map看看哪些value已经过了cooldown时间了，然后直接从map删除，这样可以维护一个cooldown size 的map

这个followup的意思就是能不能减小空间复杂度。因为task 的种类>>cooldown.势必有很多种类的task 在多个cooldown中没有被调用，这时候还在map里存着它们就是浪费空间。因为只要过了1个cooldown我们就可以再用它们，所以只用维护一个cooldown size的queue记录就好了

脸书 实习timeline

一面： 刘二姨 and follow up, 要求improve了 time and space
二面： a^n 变种, intervals 找 intersection

两次面试基本都有一个小bug，第一次硬度小哥很和善提示我了一次 很快改对了， 二面小姐姐看我卡住了3min（嘴上在bb 手停了），直接帮我把代码改了一行。。。。。。。。。。。。
本来二面完 感觉没戏了，结果一个小时后就收到了offer～ 给HR打个call！

power of n 变种， 限制使用 + - * / %

第二个是merge intervals变种 地里有

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Task%20Scheduler%20Fixed%20Order/TaskSchedulerFixedOrder.java

    // Original: HashMap O(n) O(n)
    private int withHashMap(int[] tasks, int cooldown) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int ans = 0;
        for (int task : tasks) {
            ans = Math.max(ans + 1, map.getOrDefault(task, Integer.MIN_VALUE) + cooldown + 1);
            map.put(task, ans);
        }
        return ans;
    }

    private class Task {
        int name, time;
        public Task(int name, int time) {
            this.name = name;
            this.time = time;
        }
    }

    // Follow up: Queue O(kn) O(k)
    private int withQueue(int[] tasks, int cooldown) {
        int ans = 0;
        Queue<Task> queue = new LinkedList<Task>();
        for (int task : tasks) {
            ans ++;
            for (Task rec : queue) 
                if (rec.name == task) {
                    ans = rec.time + cooldown + 1;
                    break;
                }
            while (!queue.isEmpty() && queue.peek().time < ans - cooldown)
                queue.poll();
            queue.add(new Task(task, ans));
        }
        return ans;
    }

    // Follow up: HashMap O(kn) O(k)
    private int withHashMapSizeK(int[] tasks, int cooldown) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int ans = 0;
        for (int task : tasks) {
            ans = Math.max(ans + 1, map.getOrDefault(task, Integer.MIN_VALUE) + cooldown + 1);
            List<Integer> garbage = new ArrayList<Integer>();
            for (int key : map.keySet())
                if (map.get(key) < ans - cooldown)
                    garbage.add(key);
            for (int key : garbage)
                map.remove(key);
            map.put(task, ans);
        }
        return ans;
    }

    // Follow up: Queue + HashMap O(n) O(k)
    private int withQueueAndMap(int[] tasks, int cooldown) {
        int ans = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int task : tasks) {
            ans = Math.max(ans + 1, map.getOrDefault(task, Integer.MIN_VALUE) + cooldown + 1);
            while (!queue.isEmpty() && map.get(queue.peek()) < ans - cooldown)
                map.remove(queue.poll());
            map.put(task, ans);
            queue.add(task);
        }
        return ans;
    }