621. Task Scheduler

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

My Solutions:

在每个相同的task中，必须间隔n个别的task或者idle。因此，先计算每个task的个数，然后找到频率出现最多的task的个数max，且记录有max个数的task的数量（count）。

比如AAABBBCC，A、B都出现3次，max是3且个数是3。如果n=4，则排列的最佳方式是A++++A++++A++++...把其他task填在+位置。

所以在最后一组前，每组有n+1个数字，总共需要(n+1)*(max-1)这么多位置。最后一组只有count个数字。比如上个例子中，组成的结果是[ABC+][ABC++][AB+++][AB]，最后一组只需要有AB。

需要注意的是，在AABCD，n=1的情况下，上述方法的排列是A+A+。因此，如果上述方法得到的结果小于tasks的长度，返回tasks的长度

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] table = new int[26];
        for (char c: tasks) table[(c - 'A')]++;
        
        int max = 0;
        int count = 1;
        for (int num : table) {
            if (num != 0) {
                if (max < num) {
                    max = num;
                    count = 1;
                } else if (max == num) {
                    count++;
                }
            }
        } //find the max number of occurence of task
        
        int space = (n + 1) * (max - 1) + count;
        
        if (space < tasks.length) return tasks.length;
        else return space;
    }
}