1054. 距离相等的条形码 - Java 贪心算法 任务调度思想

原题地址：https://leetcode.cn/problems/distant-barcodes/

题解

这题其实是一道简化版的任务调度器 ，对于题目中要求的“相邻数字不能重复”，我们可以立即为“不能连续填入两个相同数字”，对比到任务调度器这道题，实际上就是相当于说每个任务的冷却时间为1，由于CD只有1，这道题我们可以直接通过滚动数组来实现冷却

自然地，对于能用的未在冷却的数字，我们希望尽可能优先去用出现次数较多的数字，这样才能避免出现次数少的数字提前被用完而不得不使剩下的数字重复填入。在记录下每个数字的出现次数后，我们创建一个优先队列，按照出现次数的降序进行排列

设coolDown[0]为当前已冷却完的数字，coolDown[1]为当前进入冷却的数字

每次从优先队列取出数字时，先经过一个单位时间，将coolDown[0]设为coolDown[1]，而coolDown[1]为取出的数字，即上一个数字已经冷却完毕，当前数字开始进入冷却状态，取出数字后，将对应数字按顺序插入数组即可

更新完毕后，由于coolDown[0]已经冷却完毕，判断coolDown[0]的数字是否仍有剩余次数，若有则重新加入优先队列

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] amount=new int[10001];
        int[] ret=new int[barcodes.length];
        int itr=0;
        for (int i:barcodes){
            amount[i]++;
        }
        PriorityQueue<Integer> que=new PriorityQueue<>((Integer a,Integer b)->{return amount[b]-amount[a];});
        for (int i=1;i<=10000;i++){
            if(amount[i]!=0)que.add(i);
        }

        int[] coolDown=new int[2];
        while (!que.isEmpty()){            
            coolDown[0]=coolDown[1];
            coolDown[1]=que.remove();
            if(coolDown[0]!=0&&amount[coolDown[0]]!=0){
                que.add(coolDown[0]);
            }
            amount[coolDown[1]]--;
            ret[itr++]=coolDown[1];
        }
        return ret;
    }
}