1054. Distant Barcodes

Intuitively, we get the most frequent barcodes first which can be accomplished through max heap:

1. Each time, we get the top element of the heap and add it to the result list and decrease its frequency by one;
2. If its frequency is not zero, we save it as prev element. After one round cool down, we put non null prev back to the max heap;
3. Repeat until the heap is empty and we can get the final result.

class Number { // self-defined data structure to save the frequency of each barcodes
    int freq;
    int value;

    public Number(int freq, int value) {
        this.freq = freq;
        this.value = value;
    }
}

public int[] rearrangeBarcodes(int[] barcodes) {
    PriorityQueue<Number> queue = new PriorityQueue<Number>(new Comparator<Number>(){
       public int compare(Number n1, Number n2) {
           return n2.freq - n1.freq;
       } 
    });
    Map<Integer, Integer> numToFreq = new HashMap<Integer, Integer>();
    for(int i = 0; i < barcodes.length; i++) {
        numToFreq.put(barcodes[i], numToFreq.getOrDefault(barcodes[i], 0) + 1);
    }
    for(Map.Entry<Integer, Integer> theEntry: numToFreq.entrySet() ) {
        queue.offer(new Number(theEntry.getValue(), theEntry.getKey()));
    }
    Number prev = null;
    for(int i = 0; i < barcodes.length; i++) {
        Number n = queue.poll();
        barcodes[i] = n.value;
        n.freq--;
        if( prev != null )
            queue.offer(prev);
		
        if( n.freq > 0 ) // update prev at each round
            prev = n;
        else
            prev = null;
    }
    return barcodes;
}