（LeetCode）621. 任务调度器+字符串数组重排序

看到题目的瞬间想到了前几天做的一个类似的题目，记不太清题目了，大概题意是：将字符串数组重排序，相同的字母不能相邻。
然后细细的读了一遍题目之后发现这两道题的差别还是很大的。

---

将字符串数组重排序，相同的字母不能相邻

这个还是挺容易想到的，相同字母不相邻，那就将相同的字母每隔一个位置放一个。首先要放的是出现次数最多的，从0开始隔一个放一个（如果超过了数组的长度，那么就说明没法完成题目的要求）。然后按出现的次数从大到小依次放置。
（这道题是周二的每日一题。周二记得吧~~人工智能期末+隔天c++期末，所以只想了想思路QAQ）

---

任务调度器

今天早早地爬来了中厅，然鹅有一撮人在高声讨论峰岚，导致我的心思丝毫不在题目上，题目读了好几遍才懂（幸好有他们帮我背锅，才不是因为我没睡醒hiahiahia）

刚看完这道题就觉得与上面的题有些类似，然后就想往上面那道题上靠，觉得无非就是在相同字母之间的距离上加了个限制呗，然后开始推。

把出现次数最多的元素先按距离等于n（这个距离可以扩充）放好。

 

类似上图，此时n=4。除去最后一行的空位不确定外，其余的空位即使没有填入数据，也依然需要计入计数。当然每行也可以扩容空位。

①相同的元素放入不同的行中。因为第一列是出现次数最多的元素，所以后面的每个元素都能够放入不同行中。

②不同的元素在满足①的条件下优先填空位，然后才是选择扩充。

到现在我们可以把公式写出来了。

到此为止是我想到的，然后代码写出来，运行，结果错误。

百思不得其解

从头顺了一遍流程后没发现什么问题，然后直奔讨论区……

在这里我遇到了跟我一样读了好几遍题的同学hahah

然后发现我的公式没有问题，是这个公式没有考虑到扩充和最后一行空位的问题……

于是改进了一下（请忽略草草写的快排）

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        Arrays.fill(count,0);
        for(int i = 0;i < tasks.length;i++){
            count[tasks[i]-65]++;
        }
        //Arrays.sort(count);
        QuickSort(count,0,count.length-1);
        int num = 1;
        for(int i = 24;i>=0;i--){
            if(count[i]==count[25]){
                num++;
            }else{
                break;
            }
        }
        return Math.max(num+(count[25]-1)*(n+1),tasks.length);
    }
    public void QuickSort(int[] array,int begin,int end){
        if(begin>=end){
            return;
        }
        int i = begin;
        int j = end;
        int mid = (i+j)/2;
        int num = array[i];
        while(i<j){
            while(j>i && array[j] >= num){
                j--;
            }
            if(i<j){
                array[i] = array[j];
                i++;
            }
            while(i<j && array[i] < num){
                i++;
            }
            if(i<j){
                array[j] = array[i];
                j--;
            }
        }
        array[i] = num;
        QuickSort(array,begin,i-1);
        QuickSort(array,i+1,end);
    }
}