In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].
Rearrange the barcodes so that no two adjacent barcodes are equal.  You may return any answer, and it is guaranteed an answer exists.
Example 1:
Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]
Example 2:
Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]
Note:
1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000
from collections import Counter, defaultdict
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        memo = defaultdict(list)
        rest = 0
        for e, c in counter.most_common():
            memo[c].append(e)
            rest += c
        ret = []
        while rest:
            rest -= 1
            for c in sorted(memo.keys(), reverse=True):
                for idx, e in enumerate(memo[c]):
                    if ret and ret[-1] == e:
                        continue                
                    ret.append(e)
                    del memo[c][idx]
                    if not memo[c]:
                        del memo[c]
                    memo[c-1].append(e)
                    break
                if rest == len(barcodes) - len(ret):
                    break
                    
        return ret
from collections import Counter, defaultdict
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        memo = defaultdict(list)
        rest = 0
        for e, c in counter.most_common():
            memo[c].append(e)
            rest += c
        ret = []
        while rest:
            rest -= 1
            for c in sorted(memo.keys(), reverse=True):
                for idx, e in enumerate(memo[c]):
                    if ret and ret[-1] == e:
                        continue                
                    ret.append(e)
                    del memo[c][idx]
                    if not memo[c]:
                        del memo[c]
                    memo[c-1].append(e)
                    break
                if rest == len(barcodes) - len(ret):
                    break
                    
        return ret