CONY的世界

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

這題的思維其實蠻有趣的，一開始會想到的就是要找到 most frequency character 當作 chunk 的開頭 （類似greedy 的概念，最常出現的先開始）

然後接下來就是要思考有idle 和沒idle 的case了，所以用max 取

沒idle 的例子就是tasks.length，有idle 的例子就是 (most frequent character count -1 )* (n+1) + 與most frequent character 相同頻率的 character

我在這邊卡住在：有idle 但是塞不下的問題其實已經包含於tasks.length裡面，所以不需要再考慮              （其實就是when k>n+1，就是直接把chunk變大，但其實這就是tasks.length的情形啊）

例如： AAABBCCDD 2

AXX | AXX |           <---(most frequent character count -1 )* (n+1)           

A                            <-- 與most frequent character 相同頻率的 character ，這邊只有A

=============

ABX | ABX | 

A

=============

ABC | ABC | 

A

=============

ABCD | ABCD |           <-- 直接enlarge chunk size                  

A

但是其實這種case 就是tasks.length 的情況

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        int max_count=0;;
        int dup=1;
        for(char t: tasks){
            count[t - 'A']++;
            if(count[t - 'A'] > max_count) {
                max_count = count[t -'A'];
                dup = 1;
            } else if(count[t-'A'] == max_count)
                dup++;
        }
        return Math.max(tasks.length, (n+1)*(max_count-1)+dup);
    }
}