class Solution(object):
    def rearrangeBarcodes(self, barcodes):
        """
        :type barcodes: List[int]
        :rtype: List[int]
        """
        from collections import Counter
        import heapq
        
        record = Counter(barcodes) #ͳÿֳֵƵ
        
        queue = []
        for key, val in record.items():
            queue.append([-val, key])
            
        heapq.heapify(queue) #ȼ

        res = []
        pre = None
        while queue or pre:
            if queue:
                cur = heapq.heappop(queue) #ȡǰִԪأͬȽȳ
                #frequency, value = cur[0], cur[1]
                res.append(cur[1]) #ŵ
                cur[0] += 1 #Ƶ - 1ΪPython֧СѣΪ˴ﵽѵЧȡ෴
                if cur[0] == 0: #ԪѾź
                    cur = None
            else:
                cur = None
            if pre: #ǰһٽѲ
                heapq.heappush(queue, pre)
            pre = cur #һֵpreʱڶԱԪزظ
                
        return res
