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

Difficulty: MEDIUM
Tags: Sorting

Data structures

Mathematics

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        

Solutions:
class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if len(barcodes) < 2:
			return barcodes
		sorted_codes = sorted(barcodes)
		halfway = len(barcodes) // 2
		ans = [0] * (halfway * 2)
		(ans[::2], ans[1::2]) = (sorted_codes[-halfway:], sorted_codes[:halfway])
		if len(barcodes) % 2 == 1:
			prev = None
			mid = sorted_codes[halfway]
			for i in range(len(ans) - 1):
				if ans[i] == mid:
					i += 1
				elif ans[i] != prev:
					ans.insert(i, mid)
					break
				prev = ans[i]
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		barcodes.sort()
		n = len(barcodes)
		result = list()
		if n % 2 == 0:
			for (x, y) in zip(barcodes[:n // 2], barcodes[n // 2:]):
				result.extend([y, x])
		else:
			midVal = barcodes[n // 2]
			isAdded = False
			prev = -1
			for (x, y) in zip(barcodes[:n // 2], barcodes[n // 2 + 1:]):
				if isAdded == False and prev != midVal and (y != midVal):
					result.append(midVal)
					isAdded = True
				result.extend([y, x])
				prev = x
			if isAdded == False:
				result.append(midVal)
		return result


from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		barcodes = Counter(barcodes)
		a = []
		for (i, j) in barcodes.most_common():
			a.extend([i] * j)
		l = len(a)
		res = [0] * l
		j = 0
		for i in range(0, l, 2):
			res[i] = a[j]
			j += 1
		for i in range(1, l, 2):
			res[i] = a[j]
			j += 1
		return res


from heapq import heappush, heappop

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		hashmap = {}
		for i in range(len(barcodes)):
			key = barcodes[i]
			if key not in hashmap:
				hashmap[key] = 1
			else:
				hashmap[key] = hashmap[key] + 1
		h = []
		for (key, val) in list(hashmap.items()):
			heappush(h, (-val, key))
		result = []
		tlist = []
		while h:
			pending_lst = []
			for i in range(2):
				if h:
					(frequency, char) = heappop(h)
					positive_frequency = -frequency
					if positive_frequency > 0:
						pending_lst.append((positive_frequency - 1, char))
						if result and char == result[-1]:
							continue
						result.append(char)
			if not h and (not pending_lst):
				break
			for (frequency, char) in pending_lst:
				heappush(h, (-frequency, char))
		return result


from collections import Counter
import heapq

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = Counter(barcodes)
		pq = []
		for tup in count.items():
			heapq.heappush(pq, (-tup[1], tup[0]))
		res = []
		(prev_freq, prev_char) = (0, None)
		while pq:
			(freq, num) = heapq.heappop(pq)
			if -prev_freq > 0 and prev_char:
				heapq.heappush(pq, (prev_freq, prev_char))
			res.append(num)
			prev_freq = freq + 1
			prev_char = num
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		mp = collections.defaultdict(int)
		for b in barcodes:
			mp[b] += 1
		heap = []
		for (k, v) in list(mp.items()):
			heapq.heappush(heap, (-v, k))
		idx = 0
		n = len(barcodes)
		ans = [0] * n
		while heap:
			(f, v) = heapq.heappop(heap)
			f = -f
			while f > 0:
				ans[idx] = v
				idx += 2
				f -= 1
				if idx >= n:
					idx = 1
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = {}
		for code in barcodes:
			if code in count:
				count[code] += 1
			else:
				count[code] = 1
		count = {k: v for (k, v) in sorted(count.items(), key=lambda item: item[1], reverse=True)}
		it = iter(count.keys())
		cur = next(it)
		i = 0
		while i < len(barcodes):
			while count[cur] == 0:
				cur = next(it)
			barcodes[i] = cur
			count[cur] -= 1
			i += 2
		i = 1
		while i < len(barcodes):
			while count[cur] == 0:
				cur = next(it)
			barcodes[i] = cur
			count[cur] -= 1
			i += 2
		return barcodes


class Solution:

	def rearrangeBarcodes(self, A: List[int]) -> List[int]:
		c = collections.Counter(A)
		A.sort(key=lambda x: (c[x], x))
		(A[1::2], A[::2]) = (A[:len(A) // 2], A[len(A) // 2:])
		return A


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		dicta = collections.defaultdict(int)
		max_word = 0
		for i in barcodes:
			dicta[i] += 1
			if dicta[i] > dicta[max_word]:
				max_word = i
		n = len(barcodes)
		ans = [0 for i in range(n)]
		idx = 0
		for i in range(dicta[max_word]):
			ans[idx] = max_word
			idx += 2
		del dicta[max_word]
		for let in dicta:
			for i in range(dicta[let]):
				if idx >= n:
					idx = 1
				ans[idx] = let
				idx += 2
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = defaultdict(int)
		for i in barcodes:
			count[i] -= 1
		h = []
		for i in count:
			heappush(h, (count[i], i))
		out = [0 for _ in range(len(barcodes))]
		(freq, code) = heappop(h)
		for i in range(0, len(barcodes), 2):
			out[i] = code
			freq += 1
			if not freq and h:
				(freq, code) = heappop(h)
		if not freq and h:
			(freq, code) = heappop(h)
		for i in range(1, len(barcodes), 2):
			out[i] = code
			freq += 1
			if not freq and h:
				(freq, code) = heappop(h)
		return out


from collections import Counter
from heapq import heapify, heappop

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		c = Counter(barcodes)
		h = []
		for (k, count) in list(c.items()):
			h.append((-count, k))
		heapify(h)
		res = [0] * len(barcodes)
		index = 0
		while h:
			(count, num) = heappop(h)
			count = -count
			while count:
				if index >= len(barcodes):
					index = 1
				res[index] = num
				index += 2
				count -= 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter = collections.Counter(barcodes)
		data = [[] for i in range(len(barcodes) + 1)]
		for i in counter:
			data[counter[i]].append(i)
		res = [None for k in range(len(barcodes))]
		temp = 0
		for j in range(len(data) - 1, 0, -1):
			if len(data[j]) == 0:
				continue
			for char in data[j]:
				times = j
				while times > 0:
					res[temp] = char
					temp += 2
					times -= 1
					if temp >= len(res):
						temp = 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		dicta = [0] * 10001
		max_word = 0
		for i in barcodes:
			dicta[i] += 1
			if dicta[i] > dicta[max_word]:
				max_word = i
		ans = [0 for i in range(len(barcodes))]
		idx = 0
		for i in range(dicta[max_word]):
			ans[idx] = max_word
			idx += 2
		dicta[max_word] = 0
		for j in range(10001):
			if dicta[j] > 0:
				for i in range(dicta[j]):
					if idx >= len(barcodes):
						idx = 1
					ans[idx] = j
					idx += 2
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		n = len(barcodes)
		counter = Counter(barcodes)
		sorted_barcodes = sorted(barcodes, key=lambda x: (counter[x], x))
		res = [0] * n
		(res[1::2], res[::2]) = (sorted_barcodes[:n // 2], sorted_barcodes[n // 2:])
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		n = len(barcodes)
		if n == 1:
			return barcodes
		ans = []
		barcodes.sort()
		if n % 2 == 0:
			for (x, y) in zip(barcodes[:n // 2], barcodes[n // 2:]):
				ans.extend([y, x])
		else:
			mid = barcodes[n // 2]
			(added, x_last) = (0, -1)
			for (x, y) in zip(barcodes[:n // 2], barcodes[n // 2 + 1:]):
				if not added and x_last != mid and (y != mid):
					ans.append(mid)
					added = 1
				ans.extend([y, x])
				x_last = x
			if not added:
				ans.append(mid)
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		record = dict()
		for bar in barcodes:
			record[bar] = record.get(bar, 0) + 1
		record = sorted([(k, v) for (k, v) in record.items()], key=lambda x: x[1], reverse=True)
		max_count = record[0][1]
		read = []
		for (k, v) in record:
			read += [k] * v
		L = len(read)
		res = [[] for _ in range(max_count)]
		for idx in range(L):
			res[idx % max_count].append(read[idx])
		ress = []
		for r in res:
			ress += r
		return ress


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		len_ = len(barcodes)
		freq = collections.Counter()
		maxFreqCode = 0
		for code in barcodes:
			freq[code] += 1
			if freq[code] > freq[maxFreqCode]:
				maxFreqCode = code
		i = 0
		ans = [0] * len_
		for _ in range(freq[maxFreqCode]):
			ans[i] = maxFreqCode
			i += 2
		freq[maxFreqCode] = 0
		for code in freq:
			for _ in range(freq[code]):
				if i >= len_:
					i = 1
				ans[i] = code
				i += 2
			freq[code] = 0
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		(i, n) = (0, len(barcodes))
		res = [0] * n
		for (k, v) in collections.Counter(barcodes).most_common():
			for _ in range(v):
				res[i] = k
				i += 2
				if i >= n:
					i = 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes):
		cnt = dict()
		for v in barcodes:
			cnt[v] = cnt.get(v, 0) + 1
		N = len(barcodes)
		barcodes.sort(key=lambda v: (cnt[v], v), reverse=True)
		A = [0] * N
		(A[::2], A[1::2]) = (barcodes[:(N + 1) // 2], barcodes[(N + 1) // 2:])
		return A


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = collections.Counter(barcodes)
		barcodes.sort(key=lambda a: (count[a], a))
		(barcodes[1::2], barcodes[::2]) = (barcodes[0:len(barcodes) // 2], barcodes[len(barcodes) // 2:])
		return barcodes


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		dt = collections.Counter(barcodes)
		hp = []
		for (code, freq) in list(dt.items()):
			heapq.heappush(hp, (-freq, code))
		res = []
		while len(hp) > 1:
			(freq1, bar1) = heapq.heappop(hp)
			(freq2, bar2) = heapq.heappop(hp)
			res.append(bar1)
			res.append(bar2)
			if freq1 < -1:
				heapq.heappush(hp, (freq1 + 1, bar1))
			if freq2 < -1:
				heapq.heappush(hp, (freq2 + 1, bar2))
		if hp:
			res.append(heapq.heappop(hp)[1])
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		m = [0 for _ in range(10001)]
		max_cnt = 0
		max_n = 0
		for n in barcodes:
			m[n] += 1
			if m[n] > max_cnt:
				max_cnt = m[n]
				max_n = n
		res = [0 for _ in range(len(barcodes))]
		pos = 0
		for i in range(10001):
			n = max_n if i == 0 else i
			while m[n] > 0:
				m[n] -= 1
				res[pos] = n
				pos = pos + 2 if pos + 2 < len(barcodes) else 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		import heapq
		from collections import Counter
		cnt = Counter(barcodes)
		items = [(-v, k) for (k, v) in cnt.items()]
		heapq.heapify(items)
		res = []
		while len(items) > 1:
			(v1, k1) = heapq.heappop(items)
			v1 += 1
			(v2, k2) = heapq.heappop(items)
			v2 += 1
			res.extend([k1, k2])
			if v1 != 0:
				heapq.heappush(items, (v1, k1))
			if v2 != 0:
				heapq.heappush(items, (v2, k2))
		if len(items) == 1:
			res.append(items[0][1])
		return res


from collections import Counter
import heapq as q

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		c = Counter(barcodes)
		xs = []
		for (k, v) in list(c.items()):
			q.heappush(xs, (-v, k))
		r = []
		while len(xs) > 1:
			(av, ak) = q.heappop(xs)
			(bv, bk) = q.heappop(xs)
			r.append(ak)
			r.append(bk)
			av += 1
			bv += 1
			if av < 0:
				q.heappush(xs, (av, ak))
			if bv < 0:
				q.heappush(xs, (bv, bk))
		if len(xs) == 0:
			return r
		(av, ak) = q.heappop(xs)
		r.append(ak)
		return r


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		c = collections.Counter(barcodes)
		heap = []
		for (cha, time) in list(c.items()):
			heapq.heappush(heap, (-time, cha))
		res = []
		while heap:
			n = len(heap)
			if n >= 2:
				(t1, c1) = heapq.heappop(heap)
				res.append(c1)
				(t2, c2) = heapq.heappop(heap)
				res.append(c2)
				if t1 + 1 < 0:
					heapq.heappush(heap, (t1 + 1, c1))
				if t2 + 1 < 0:
					heapq.heappush(heap, (t2 + 1, c2))
			else:
				(t, c) = heapq.heappop(heap)
				res.append(c)
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		h = []
		c = collections.Counter(barcodes)
		for i in c:
			heapq.heappush(h, (-c[i], i))
		res = []
		if len(barcodes) < 2:
			return str(barcodes[0])
		while h:
			(val1, char1) = heapq.heappop(h)
			char2 = ''
			if h:
				(val2, char2) = heapq.heappop(h)
			res.append(char1)
			res.append(char2)
			if val1 * -1 > 1:
				heapq.heappush(h, (val1 + 1, char1))
			if val2 * -1 > 1:
				heapq.heappush(h, (val2 + 1, char2))
		return res


from heapq import heappush, heappop
from collections import defaultdict

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq = defaultdict(int)
		for code in barcodes:
			freq[code] += 1
		(maxH, res) = ([], [])
		for (num, count) in freq.items():
			heappush(maxH, (-count, num))
		while maxH:
			(count1, num1) = heappop(maxH)
			count1 += 1
			res.append(num1)
			if maxH:
				(count2, num2) = heappop(maxH)
				res.append(num2)
				count2 += 1
				if count2 < 0:
					heappush(maxH, (count2, num2))
			if count1 < 0:
				heappush(maxH, (count1, num1))
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter = Counter(barcodes)
		heap = [(-v, c) for (c, v) in counter.items()]
		heapq.heapify(heap)
		res = []
		while heap:
			popped = []
			for _ in range(2):
				if not heap:
					return res
				(v, c) = heapq.heappop(heap)
				res.append(c)
				if v < -1:
					popped.append([v + 1, c])
			for (v, c) in popped:
				heapq.heappush(heap, (v, c))
		return res


from collections import defaultdict
import heapq

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		d = defaultdict(int)
		heap = []
		res = []
		for bc in barcodes:
			d[bc] += 1
		for (key, val) in d.items():
			heapq.heappush(heap, (-val, key))
		while heap:
			cur = heapq.heappop(heap)
			if res and res[-1] == cur[1]:
				tmp = heapq.heappop(heap)
				res.append(tmp[1])
				val = 1 + tmp[0]
				if val != 0:
					heapq.heappush(heap, (val, tmp[1]))
				heapq.heappush(heap, cur)
			else:
				res.append(cur[1])
				v = cur[0] + 1
				if v != 0:
					heapq.heappush(heap, (v, cur[1]))
		return res


from collections import Counter, deque
from heapq import *

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = Counter(barcodes)
		res = []
		maxHeap = []
		for (num, freq) in list(count.items()):
			heappush(maxHeap, (-freq, num))
		q = deque([])
		while maxHeap:
			(negCnt, num) = heappop(maxHeap)
			res.append(num)
			q.append((negCnt, num))
			if len(q) == 2:
				(negCnt, num) = q.popleft()
				negCnt += 1
				if negCnt < 0:
					heappush(maxHeap, (negCnt, num))
		return res


import heapq as hq
from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter = Counter(barcodes)
		cqueue = [(-v, k) for (k, v) in list(counter.items())]
		hq.heapify(cqueue)
		res = []
		while len(cqueue) > 0:
			(neg_count, barcode) = hq.heappop(cqueue)
			if len(res) != 0 and res[-1] == barcode:
				(neg_count_2, barcode_2) = hq.heappop(cqueue)
				hq.heappush(cqueue, (neg_count, barcode))
				(neg_count, barcode) = (neg_count_2, barcode_2)
			res.append(barcode)
			if neg_count != -1:
				hq.heappush(cqueue, (neg_count + 1, barcode))
		return res


import heapq

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = {}
		for i in barcodes:
			if i not in count:
				count[i] = 0
			count[i] += 1
		heap = [(-v, k) for (k, v) in list(count.items())]
		heapq.heapify(heap)
		op = [None]
		i = 0
		while heap:
			temp = []
			while True:
				(maxVal, maxKey) = heapq.heappop(heap)
				if maxKey == op[-1]:
					temp.append((maxVal, maxKey))
				else:
					break
			op.append(maxKey)
			currVal = maxVal + 1
			if currVal < 0:
				heapq.heappush(heap, (currVal, maxKey))
			while temp:
				(val, key) = temp.pop()
				heapq.heappush(heap, (val, key))
		return op[1:]


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = defaultdict(int)
		for i in barcodes:
			count[i] += 1
		heap = []
		for (key, val) in list(count.items()):
			heap.append([-val, key])
		heapq.heapify(heap)
		idx = 0
		while len(heap) > 1:
			one = heapq.heappop(heap)
			two = heapq.heappop(heap)
			barcodes[idx] = one[1]
			idx += 1
			barcodes[idx] = two[1]
			idx += 1
			one[0] += 1
			two[0] += 1
			if one[0] != 0:
				heapq.heappush(heap, one)
			if two[0] != 0:
				heapq.heappush(heap, two)
		if heap:
			barcodes[idx] = heapq.heappop(heap)[1]
		return barcodes


from heapq import heappush, heappop, heapify

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter = Counter(barcodes)
		i = 0
		for (n, count) in counter.most_common():
			for _ in range(count):
				barcodes[i] = n
				i += 2
				if i >= len(barcodes):
					i = 1
		return barcodes


class Solution:

	def update(self, freq, key, heap):
		if freq > 1:
			heappush(heap, (-1 * (freq - 1), key))

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq_map = defaultdict(int)
		heap = []
		res = []
		for n in barcodes:
			freq_map[n] += 1
		for key in list(freq_map.keys()):
			heappush(heap, (-1 * freq_map[key], key))
		while len(heap) > 0:
			(freq_a, key_a) = heappop(heap)
			res.append(key_a)
			if len(heap) == 0:
				break
			(freq_b, key_b) = heappop(heap)
			res.append(key_b)
			self.update(-1 * freq_a, key_a, heap)
			self.update(-1 * freq_b, key_b, heap)
		return res


import heapq
from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counts = Counter(barcodes)
		arr = [[-v, k] for (k, v) in list(counts.items())]
		heapq.heapify(arr)
		newBarcodes = []
		while len(arr) != 0:
			elem1 = heapq.heappop(arr)
			newBarcodes.append(elem1[1])
			if len(arr) == 0:
				return newBarcodes
			elem2 = heapq.heappop(arr)
			newBarcodes.append(elem2[1])
			elem1[0] += 1
			if elem1[0] < 0:
				heapq.heappush(arr, elem1)
			elem2[0] += 1
			if elem2[0] < 0:
				heapq.heappush(arr, elem2)
		return newBarcodes


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		h = collections.Counter(barcodes)
		heap = [(-value, key) for (key, value) in list(h.items())]
		heapq.heapify(heap)
		a = []
		while heap:
			x = heapq.heappop(heap)
			if heap == []:
				a.append(x[1])
				return a
			y = heapq.heappop(heap)
			a.append(x[1])
			a.append(y[1])
			if x[0] + 1 != 0:
				heapq.heappush(heap, (x[0] + 1, x[1]))
			if y[0] + 1 != 0:
				heapq.heappush(heap, (y[0] + 1, y[1]))
		return a


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq = {}
		for b in barcodes:
			if b in freq:
				freq[b] += 1
			else:
				freq[b] = 1
		descBarcode = sorted([(k, v) for (k, v) in list(freq.items())], key=lambda i: i[1], reverse=True)
		newBarcode = []
		maxIncrements = descBarcode[0][1]
		(curIndex, curIncrements) = (1, 0)
		for (num, count) in descBarcode:
			if not newBarcode:
				newBarcode = [num] * count
			else:
				while count > 0:
					newBarcode.insert(curIndex, num)
					curIndex += 2
					maxIncrements += 1
					if curIncrements > maxIncrements or curIndex > len(newBarcode):
						curIndex = 1
						maxIncrements = 0
					count -= 1
		return newBarcode


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if len(barcodes) < 2:
			return barcodes
		counter = collections.Counter(barcodes)
		heap = []
		for (k, v) in counter.items():
			heapq.heappush(heap, (-v, k))
		result = []
		while len(heap) > 1:
			(count1, key1) = heapq.heappop(heap)
			(count2, key2) = heapq.heappop(heap)
			result.append(key1)
			result.append(key2)
			count1 += 1
			count2 += 1
			if count1 < 0:
				heapq.heappush(heap, (count1, key1))
			if count2 < 0:
				heapq.heappush(heap, (count2, key2))
		print(heap)
		if len(heap) > 0:
			(count, key) = heapq.heappop(heap)
			result.append(key)
			return result
		else:
			return result


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq = [0] * 10001
		maxFreqCode = 0
		for code in barcodes:
			freq[code] += 1
			if freq[code] > freq[maxFreqCode]:
				maxFreqCode = code
		(i, n) = (0, len(barcodes))
		ans = [0] * n
		for code in range(10001):
			if code == 0:
				code = maxFreqCode
			for _ in range(freq[code]):
				if i >= n:
					i = 1
				ans[i] = code
				i += 2
			freq[code] = 0
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq = {}
		for b in barcodes:
			if b in freq:
				freq[b] += 1
			else:
				freq[b] = 1
		frqBarcode = [(k, v) for (k, v) in list(freq.items())]
		(maxNum, maxIncrements) = max(frqBarcode, key=lambda i: i[1])
		newBarcode = [maxNum] * maxIncrements
		(curIndex, curIncrements) = (1, 0)
		for (num, count) in frqBarcode:
			if num == maxNum:
				continue
			while count > 0:
				newBarcode.insert(curIndex, num)
				curIndex += 2
				maxIncrements += 1
				if curIncrements > maxIncrements or curIndex > len(newBarcode):
					curIndex = 1
					maxIncrements = 0
				count -= 1
		return newBarcode


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		h = []
		d = defaultdict(int)
		for ele in barcodes:
			d[ele] += 1
		for (key, val) in d.items():
			heappush(h, (-1 * val, key))
		res = []
		prev = ()
		while h:
			ele = heappop(h)
			freq = ele[0] * -1
			res.append(ele[1])
			if prev != ():
				heappush(h, prev)
			if freq != 1:
				prev = (-1 * (freq - 1), ele[1])
			else:
				prev = ()
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		hq = [(-v, i) for (i, v) in collections.Counter(barcodes).items()]
		heapq.heapify(hq)
		res = []
		while hq:
			temp = []
			for _ in range(min(len(hq), 2)):
				(val, number) = heapq.heappop(hq)
				temp.append((val, number))
				res.append(number)
			for _ in range(len(temp)):
				(val, number) = temp.pop()
				if val < -1:
					heapq.heappush(hq, (val + 1, number))
		return res


from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freqs = Counter(barcodes)
		result = [-1] * len(barcodes)
		i = 0
		for (bc, c) in sorted(freqs.items(), key=lambda x: -x[1]):
			for _ in range(c):
				if i >= len(result):
					i = 1
				result[i] = bc
				i += 2
		return result


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if len(barcodes) <= 1:
			return barcodes

		def helper(barcodes, k):
			freqCount = collections.defaultdict(int)
			for ele in barcodes:
				freqCount[ele] += 1
			result = []
			cooldown = collections.deque()
			heap = []
			for (key, value) in freqCount.items():
				heapq.heappush(heap, (-value, key))
			while len(heap) > 0:
				(count, element) = heapq.heappop(heap)
				count *= -1
				result.append(element)
				cooldown.append((count - 1, element))
				if len(cooldown) < k:
					continue
				(cooldownCount, cooldownElement) = cooldown.popleft()
				if cooldownCount > 0:
					heapq.heappush(heap, (-cooldownCount, cooldownElement))
			return result
		return helper(barcodes, 2)


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counts = {k: 0 for k in barcodes}
		for n in barcodes:
			counts[n] += 1
		barcodes.sort()
		barcode = []
		heap = [(-y, x) for (x, y) in list(counts.items())]
		heapq.heapify(heap)
		print(heap)
		while len(heap) > 0:
			(freq, digit) = heapq.heappop(heap)
			if len(barcode) == 0 or barcode[-1] != digit:
				barcode.append(digit)
				if freq < -1:
					freq += 1
					heapq.heappush(heap, (freq, digit))
			else:
				(nextFreq, nextDig) = heapq.heappop(heap)
				barcode.append(nextDig)
				heapq.heappush(heap, (freq, digit))
				if nextFreq < -1:
					nextFreq += 1
					heapq.heappush(heap, (nextFreq, nextDig))
		return barcode


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		cnts = collections.defaultdict(int)
		for n in barcodes:
			cnts[n] += 1
		barcodes.sort(key=lambda x: (cnts[x], x))
		n = len(barcodes)
		(first, second) = (barcodes[:n // 2], barcodes[n // 2:])
		res = []
		(f, s) = (0, 0)
		while f < len(first) or s < len(second):
			if s < len(second):
				res.append(second[s])
				s += 1
			if f < len(first):
				res.append(first[f])
				f += 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		q = [[-v, k] for (k, v) in collections.Counter(barcodes).items()]
		heapq.heapify(q)
		result = []
		while q:
			if result and result[-1] == q[0][1]:
				tmp = heapq.heappop(q)
				item = heapq.heappop(q)
				result.append(item[1])
				item[0] += 1
				if item[0] < 0:
					heapq.heappush(q, item)
				heapq.heappush(q, tmp)
			else:
				item = heapq.heappop(q)
				result.append(item[1])
				item[0] += 1
				if item[0] < 0:
					heapq.heappush(q, item)
		return result


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


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if len(barcodes) <= 1:
			return barcodes
		counts = defaultdict(int)
		for b in barcodes:
			counts[b] += 1
		max_count = 0
		max_b = 0
		for (b, c) in counts.items():
			if c > max_count:
				max_count = c
				max_b = b
		everything_else = [b for b in barcodes if b != max_b]
		arranged = [max_b] * max_count
		i = 1
		while i <= len(arranged) and len(everything_else) != 0:
			arranged.insert(i, everything_else.pop(0))
			i += 2

		def can_add_at(i, b):
			if i == 0:
				return arranged[i] != b
			elif i == len(arranged):
				return arranged[-1] != b
			else:
				return arranged[i] != b and arranged[i - 1] != b
		i = 0
		while len(everything_else) != 0:
			if can_add_at(i, everything_else[0]):
				arranged.insert(i, everything_else.pop(0))
			i += 1
		return arranged


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		queue = deque()
		heap = []
		d = {}
		res = []
		time = 0
		for code in barcodes:
			d[code] = d.get(code, 0) - 1
		for (k, v) in d.items():
			heapq.heappush(heap, (v, k))
		while heap or queue:
			if heap:
				(count, code) = heapq.heappop(heap)
				count += 1
				res.append(code)
				if count < 0:
					queue.append([time + 1, (count, code)])
			if queue and queue[0][0] <= time:
				heapq.heappush(heap, queue.popleft()[1])
			time += 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		import heapq
		n = len(barcodes)
		d = {}
		for x in barcodes:
			if d.get(x) != None:
				d[x] += 1
			else:
				d[x] = 1
		barcodes = []
		for x in list(d.keys()):
			heapq.heappush(barcodes, (-d[x], x))
		ans = []
		for x in range(n):
			temp = []
			if ans == []:
				curr = heapq.heappop(barcodes)
				ans.append(curr[1])
				if curr[0] != -1:
					heapq.heappush(barcodes, (curr[0] + 1, curr[1]))
			else:
				while True:
					curr = heapq.heappop(barcodes)
					if ans[-1] != curr[1]:
						ans.append(curr[1])
						if curr[0] != -1:
							heapq.heappush(barcodes, (curr[0] + 1, curr[1]))
						break
					else:
						temp.append(curr)
				while len(temp):
					heapq.heappush(barcodes, temp.pop())
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		l = barcodes[:]
		n = len(l)
		c = Counter(l)
		c = list(sorted(list(c.items()), key=lambda x: -x[1]))
		nl = [0] * n
		y = 0
		x = c[y][1]
		val = c[y][0]
		for i in range(0, n, 2):
			nl[i] = val
			x -= 1
			if x == 0:
				y += 1
				if y < len(c):
					x = c[y][1]
					val = c[y][0]
		for i in range(1, n, 2):
			nl[i] = val
			x -= 1
			if x == 0:
				y += 1
				if y < len(c):
					x = c[y][1]
					val = c[y][0]
		return nl


import heapq
from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		ans = []
		c = Counter(barcodes)
		heap = []
		for b in c:
			heapq.heappush(heap, (-c[b], b))
		while heap:
			temp = heapq.heappop(heap)
			if ans and ans[-1] == temp[1]:
				temp2 = heapq.heappop(heap)
				ans.append(temp2[1])
				heapq.heappush(heap, (temp[0], temp[1]))
				if temp2[0] < -1:
					heapq.heappush(heap, (temp2[0] + 1, temp2[1]))
			else:
				ans.append(temp[1])
				if temp[0] < -1:
					heapq.heappush(heap, (temp[0] + 1, temp[1]))
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		d = collections.Counter(barcodes)
		res = []
		pq = []
		for (no, f) in list(d.items()):
			heapq.heappush(pq, [-f, no])
		temp = []
		while len(pq) != 0 or temp != 0:
			if len(pq) != 0:
				(f, no) = heapq.heappop(pq)
				if temp != []:
					heapq.heappush(pq, temp)
					temp = []
			elif temp != []:
				(f, no) = temp
				temp = []
			else:
				break
			f = f * -1
			f = f - 1
			res.append(no)
			if f != 0:
				if len(pq) == 0:
					heapq.heappush(pq, [-f, no])
				elif -f > pq[0][0]:
					heapq.heappush(pq, [-f, no])
				else:
					temp = [-f, no]
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		d = Counter(barcodes)
		cand = barcodes[0]
		maxi = d[cand]
		for (idx, (k, v)) in enumerate(d.items()):
			if v > maxi:
				maxi = v
				cand = k
		res = [None for i in range(len(barcodes))]
		pos = 0
		for i in range(maxi):
			res[pos] = cand
			pos += 2
		del d[cand]
		for (idx, (k, v)) in enumerate(d.items()):
			for j in range(v):
				if pos >= len(res):
					pos = 1
				res[pos] = k
				pos += 2
		return res


import heapq
from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		c = Counter(barcodes)
		heap = []
		res = []
		for (key, val) in list(c.items()):
			heap.append((-val, key))
		heapq.heapify(heap)
		prevCnt = 0
		while heap:
			(cnt, code) = heapq.heappop(heap)
			cnt = -cnt
			res.append(code)
			if prevCnt > 0:
				heapq.heappush(heap, (-prevCnt, prevCode))
			prevCnt = cnt - 1
			prevCode = code
		return res


import collections
from heapq import heappush, heappop

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		elementCountMap = collections.Counter(barcodes)
		elementStack = []
		for (element, count) in list(elementCountMap.items()):
			heappush(elementStack, [-count, element])
		result = []
		previousElement = None
		while elementStack:
			tmp = None
			(count, element) = heappop(elementStack)
			if element == previousElement:
				tmp = [count, element]
				(count, element) = heappop(elementStack)
			result.append(element)
			previousElement = element
			count += 1
			if count < 0:
				heappush(elementStack, [count, element])
			if tmp:
				heappush(elementStack, tmp)
		return result


import heapq
from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		maxheap = []
		K = 0
		map1 = Counter(barcodes)
		index = 0
		for (k, v) in list(map1.items()):
			heappush(maxheap, (-v, k))
		res = [0] * len(barcodes)
		while len(maxheap) > 0:
			element = heappop(maxheap)
			res[index] = element[1]
			if len(maxheap) == 0:
				break
			index += 1
			element2 = heappop(maxheap)
			res[index] = element2[1]
			self.updateMap(map1, maxheap, element)
			self.updateMap(map1, maxheap, element2)
			index += 1
		return res

	def updateMap(self, map1, maxheap, element):
		if map1[element[1]] == 1:
			del map1[element[1]]
		else:
			map1[element[1]] = map1[element[1]] - 1
			heappush(maxheap, (-map1[element[1]], element[1]))


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = Counter(barcodes)
		heap = [(-count[x], x) for x in list(count.keys())]
		heapq.heapify(heap)
		out = []
		while len(heap) > 1:
			(count1, code1) = heapq.heappop(heap)
			(count2, code2) = heapq.heappop(heap)
			out.extend([code1, code2])
			count1 += 1
			count2 += 1
			if count1 < 0:
				heapq.heappush(heap, (count1, code1))
			if count2 < 0:
				heapq.heappush(heap, (count2, code2))
		if heap:
			(count1, code1) = heapq.heappop(heap)
			out += [code1]
		return out


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		cnts = collections.Counter(barcodes)
		heap = [(-v, k) for (k, v) in list(cnts.items())]
		heapq.heapify(heap)
		res = []
		while heap:
			(cnt1, num1) = heapq.heappop(heap)
			if res and res[-1] == num1:
				(cnt, num) = heapq.heappop(heap)
				res.append(num)
				cnt += 1
				if cnt != 0:
					heapq.heappush(heap, (cnt, num))
				res.append(num1)
				cnt1 += 1
				if cnt1 != 0:
					heapq.heappush(heap, (cnt1, num1))
			else:
				res.append(num1)
				cnt1 += 1
				if cnt1 != 0:
					heapq.heappush(heap, (cnt1, num1))
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		d = defaultdict(lambda : 0)
		for b in barcodes:
			d[b] += 1
		counter = 0
		heap = []
		for b in d:
			heap.append((-d[b], counter, b))
			counter += 1
		heapify(heap)
		result = []
		while heap:
			(count1, tmp, b1) = heappop(heap)
			result.append(b1)
			if not heap:
				return result
			(count2, tmp, b2) = heappop(heap)
			result.append(b2)
			count1 += 1
			count2 += 1
			if count1:
				heappush(heap, (count1, counter, b1))
				counter += 1
			if count2:
				heappush(heap, (count2, counter, b2))
				counter += 1
		return result


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq = dict()
		for i in range(len(barcodes)):
			freq[barcodes[i]] = freq.get(barcodes[i], 0) + 1
		heap = list()
		reverse = collections.defaultdict(list)
		for el in freq:
			heap.append(-freq[el])
			reverse[freq[el]].append(el)
		heapq.heapify(heap)
		temp_list = list()
		answer = list()
		while True:
			if len(temp_list) > 1:
				temp = temp_list.pop(0)
				if temp[0] > 0:
					heapq.heappush(heap, -temp[0])
					reverse[temp[0]].append(temp[1])
			if len(heap) > 0:
				cur_freq = -heapq.heappop(heap)
				cur_el = reverse[cur_freq].pop(0)
				answer.append(cur_el)
				temp_list.append([cur_freq - 1, cur_el])
			else:
				break
		while len(temp_list) > 0:
			temp = temp_list.pop(0)
			if temp[0] > 0:
				answer.append(temp[1])
		return answer


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = collections.Counter(barcodes)
		ans = [0] * len(barcodes)
		index = 0
		for (key, freq) in count.most_common():
			for _ in range(freq):
				if index >= len(barcodes):
					index = 1
				ans[index] = key
				index += 2
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		import heapq
		from collections import defaultdict
		d = defaultdict(int)
		for i in barcodes:
			d[i] += 1
		h = []
		for i in d:
			h.append((-d[i], i))
		heapq.heapify(h)
		ans = []
		while len(h) > 1:
			(c1, val1) = heapq.heappop(h)
			(c2, val2) = heapq.heappop(h)
			c1 += 1
			c2 += 1
			ans.append(val1)
			ans.append(val2)
			if c1:
				heapq.heappush(h, (c1, val1))
			if c2:
				heapq.heappush(h, (c2, val2))
		if h:
			ans.append(heapq.heappop(h)[1])
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		c = Counter(barcodes)
		heap = []
		ans = []
		for (k, v) in c.items():
			heapq.heappush(heap, (-v, k))
		while heap:
			(most, d1) = heapq.heappop(heap)
			if ans and ans[-1] == d1:
				(more, d2) = heapq.heappop(heap)
				ans.append(d2)
				if more < -1:
					heapq.heappush(heap, (more + 1, d2))
				heapq.heappush(heap, (most, d1))
				continue
			ans.append(d1)
			if most < -1:
				heapq.heappush(heap, (most + 1, d1))
		return ans


import collections

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		dic = {}
		lst = [0] * len(barcodes)
		for i in barcodes:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		sorted_x = sorted(dic.items(), key=lambda kv: kv[1], reverse=True)
		sorted_dict = collections.OrderedDict(sorted_x)
		var = 0
		for (i, j) in sorted_dict.items():
			for _ in range(j):
				lst[var] = i
				var += 2
				if var >= len(barcodes):
					var = 1
		return lst


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if not barcodes:
			return []
		res = [None] * len(barcodes)
		barCount = collections.defaultdict(int)
		for barcode in barcodes:
			barCount[barcode] += 1
		mostFreq = max(barCount, key=barCount.get)
		i = 0
		for _ in range(barCount[mostFreq]):
			res[i] = mostFreq
			i += 2
		if i >= len(barcodes):
			i = 1
		barSet = set(barcodes)
		barSet.remove(mostFreq)
		for key in barSet:
			if key == mostFreq:
				continue
			for _ in range(barCount[key]):
				res[i] = key
				i += 2
				if i >= len(barcodes):
					i = 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter = Counter(barcodes)
		keys = sorted(list(counter.keys()), key=lambda k: counter[k], reverse=True)
		numbers = []
		for key in keys:
			numbers.extend([key] * counter[key])
		ans = [0] * len(numbers)
		N = len(numbers)
		ans[::2] = numbers[:(N + 1) // 2]
		ans[1::2] = numbers[(N + 1) // 2:]
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		cnt = Counter(barcodes)
		M = 0
		for (k, v) in cnt.items():
			if v > M:
				mark = k
				M = v
		barcodes.sort()
		pos = defaultdict(list)
		j = 0
		for i in range(len(barcodes)):
			if barcodes[i] != mark:
				pos[j].append(barcodes[i])
				j = (j + 1) % M
		ans = []
		for i in range(M):
			ans += [mark] + pos[i]
		return ans


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		count = Counter(barcodes)
		pq = []
		for c in count:
			heappush(pq, [-count[c], c])
		output = []
		prev = None
		while pq:
			(c, v) = heappop(pq)
			c += 1
			output.append(v)
			if prev:
				heappush(pq, prev)
				prev = None
			if c != 0:
				prev = [c, v]
		return output


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter = collections.Counter(barcodes)
		pq = []
		for (key, value) in counter.items():
			heapq.heappush(pq, (-value, key))
		temp_list = []
		result = []
		while pq:
			k = 2
			while pq and k > 0:
				(count, curr) = heapq.heappop(pq)
				count = count * -1
				result.append(curr)
				if count > 1:
					temp_list.append((count - 1, curr))
				k -= 1
			if len(temp_list) == 0 and len(pq) == 0:
				break
			while temp_list:
				(count, curr) = temp_list.pop()
				heapq.heappush(pq, (-count, curr))
		return result


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counter_dict = collections.Counter(barcodes)
		kk_heap = []
		for it in list(counter_dict.items()):
			heapq.heappush(kk_heap, [-it[1], it[0]])
		last_kk = None
		res = []
		while kk_heap:
			if len(kk_heap) == 1:
				res.append(kk_heap[0][1])
				break
			choose_from = [heapq.heappop(kk_heap), heapq.heappop(kk_heap)]
			idx = 0 if last_kk != choose_from[0][1] else 1
			kk = choose_from[idx][1]
			res.append(kk)
			choose_from[idx][0] += 1
			for cf in choose_from:
				if cf[0]:
					heapq.heappush(kk_heap, cf)
			last_kk = kk
		return res


class Solution:

	def rearrangeBarcodes(self, S: List[int]) -> List[int]:
		if not S:
			return []
		d = collections.Counter(S)
		heap = []
		for (key, value) in list(d.items()):
			heapq.heappush(heap, [-value, key])
		res = []
		pre = heapq.heappop(heap)
		res.append(pre[1])
		while heap:
			cur = heapq.heappop(heap)
			res.append(cur[1])
			pre[0] += 1
			if pre[0] < 0:
				heapq.heappush(heap, pre)
			pre = cur
		if len(res) != len(S):
			return []
		else:
			return res


from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		counts = Counter(barcodes)
		n = len(barcodes)
		res = [0] * n
		i = 0
		for (k, v) in counts.most_common():
			while v > 0:
				res[i] = k
				i += 2
				v -= 1
				if i > n - 1:
					i = 1
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		import collections
		import heapq
		c_dic = collections.Counter(barcodes)
		hp = []
		for key in c_dic:
			heapq.heappush(hp, (-c_dic[key], key))
		res = []
		while hp:
			collect = []
			if res:
				while hp[0][1] == res[-1]:
					cur = heapq.heappop(hp)
					collect.append(cur)
			cur = heapq.heappop(hp)
			res.append(cur[1])
			if cur[0] != -1:
				heapq.heappush(hp, (cur[0] + 1, cur[1]))
			for nodes in collect:
				heapq.heappush(hp, nodes)
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		cb = collections.Counter(barcodes)
		for (kk, l) in cb.most_common():
			out = [[kk] for _ in range(l)]
			break
		i = 0
		for k in cb:
			if k != kk:
				for v in range(cb[k]):
					out[i % l].append(k)
					i += 1
		output = []
		for o in out:
			output += o
		return output


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if len(barcodes) <= 1:
			return barcodes
		(heap, res) = ([], [])
		counter = collections.Counter(barcodes)
		for (val, cnt) in counter.items():
			heapq.heappush(heap, (-cnt, val))
		res = []
		while len(heap) > 1:
			(cnt1, val1) = heapq.heappop(heap)
			(cnt2, val2) = heapq.heappop(heap)
			res.extend([val1, val2])
			cnt1 += 1
			cnt2 += 1
			if cnt1:
				heapq.heappush(heap, (cnt1, val1))
			if cnt2:
				heapq.heappush(heap, (cnt2, val2))
		if heap:
			res.append(heap[0][1])
		return res


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		freq = collections.Counter(barcodes)
		heap = []
		for (k, v) in freq.items():
			heapq.heappush(heap, (-v, k))
		ans = []
		while heap:
			(freq, num) = heapq.heappop(heap)
			if not ans:
				ans.append(num)
				freq += 1
				if freq < 0:
					heapq.heappush(heap, (freq, num))
			elif num == ans[-1]:
				(nextFreq, nextNum) = heapq.heappop(heap)
				ans.append(nextNum)
				nextFreq += 1
				if nextFreq < 0:
					heapq.heappush(heap, (nextFreq, nextNum))
				heapq.heappush(heap, (freq, num))
			else:
				ans.append(num)
				freq += 1
				if freq < 0:
					heapq.heappush(heap, (freq, num))
		return ans


from collections import Counter

class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if barcodes is None or len(barcodes) == 0:
			return []
		if len(barcodes) == 1:
			return barcodes
		counter = Counter(barcodes)
		num_occurrences = sorted(counter, key=lambda x: counter.get(x), reverse=True)
		elements = dict()
		for elem in num_occurrences:
			elements[elem] = counter[elem]
		output = [None] * len(barcodes)
		item_index = 0
		index = 0
		value = num_occurrences[0]
		value_index = 0
		for i in range(len(barcodes)):
			while output[index] is not None or output[index - 1] == value:
				index += 1
				index %= len(barcodes)
			output[index] = value
			item_index += 1
			index += 1
			index %= len(barcodes)
			if elements[value] == 1:
				value_index += 1
				if value_index >= len(num_occurrences):
					return output
				value = num_occurrences[value_index]
			else:
				elements[value] -= 1
		return output


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		if barcodes is None or len(barcodes) == 0:
			return []
		n = len(barcodes)
		dict_t = {}
		for i in range(n):
			temp = barcodes[i]
			dict_t[temp] = dict_t.get(temp, 0) + 1
		hp = []
		for (key, value) in dict_t.items():
			heapq.heappush(hp, (-value, key))
		result = []
		count1 = 0
		count2 = 0
		while hp:
			(count1, key1) = heapq.heappop(hp)
			if hp:
				(count2, key2) = heapq.heappop(hp)
			if count1 < 0 and count2 < 0:
				result.append(key1)
				result.append(key2)
				count1 += 1
				count2 += 1
			elif count1 < 0 and count2 == 0:
				result.append(key1)
				count1 += 1
			if count1 < 0:
				heapq.heappush(hp, (count1, key1))
			if count2 < 0:
				heapq.heappush(hp, (count2, key2))
		return result


class Solution:

	def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
		hash_map = dict()
		heap = list()
		result = [0] * len(barcodes)
		index = 0
		for bar_code in barcodes:
			hash_map[bar_code] = hash_map.get(bar_code, 0) + 1
		print(hash_map)
		for (code, freq) in hash_map.items():
			heap.append((-freq, code))
		heapq.heapify(heap)
		while heap:
			(freq, code) = heapq.heappop(heap)
			freq = abs(freq)
			while freq > 0:
				if index >= len(barcodes):
					index = 1
				result[index] = code
				index += 2
				freq -= 1
		return result