1054. Distant Barcodes | 1702

 1class Solution:
 2    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
 3        # intuition
 4        # store barcodes in a dict
 5        # basically iter dict until exhaustion
 6
 7        # e.g. {1: 3,
 8        #       2: 4}
 9        # we MUST put 2 at the beginning, thus intuition fails
10
11        # we will not fail if we always try to put the most abundant number
12        # e.g. 1: 3, 2: 5, 3: 4, 4: 3
13        # 2, 3, 2, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4
14        # need a way to keep track and skip the last barcode
15
16        pq = [(-count, barcode) for barcode, count in Counter(barcodes).items()]
17        heapq.heapify(pq)  # heapify first before pop
18        prev_barcode = -1
19        result = []
20
21        while pq:
22            neg_count, barcode = heapq.heappop(pq)
23
24            if barcode == prev_barcode:  # pq is guaranteed to have items
25                pending_push = (neg_count, barcode)
26                neg_count, barcode = heapq.heappop(pq)
27                heapq.heappush(pq, pending_push)
28
29            prev_barcode = barcode
30
31            result.append(barcode)
32            if neg_count < -1:  # only push back if still contains barcode
33                heapq.heappush(pq, (neg_count + 1, barcode))
34
35        return result