Distant Barcodes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> cnt;
        for (int b : barcodes) cnt[b]++;
        priority_queue<pair<int, int>> pq;
        for (auto& [k, v] : cnt) pq.push({v, k});
        vector<int> ans;
        while (pq.size() > 1) {
            auto [c1, n1] = pq.top(); pq.pop();
            auto [c2, n2] = pq.top(); pq.pop();
            ans.push_back(n1);
            ans.push_back(n2);
            if (--c1) pq.push({c1, n1});
            if (--c2) pq.push({c2, n2});
        }
        if (!pq.empty()) ans.push_back(pq.top().second);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func rearrangeBarcodes(barcodes []int) []int {
    cnt := map[int]int{}
    for _, b := range barcodes {
        cnt[b]++
    }
    type pair struct{ c, n int }
    pq := &[]pair{}
    for n, c := range cnt {
        *pq = append(*pq, pair{c, n})
    }
    sort.Slice(*pq, func(i, j int) bool { return (*pq)[i].c > (*pq)[j].c })
    ans := make([]int, 0, len(barcodes))
    for len(*pq) > 1 {
        p1, p2 := (*pq)[0], (*pq)[1]
        ans = append(ans, p1.n, p2.n)
        (*pq)[0].c--
        (*pq)[1].c--
        tmp := []pair{}
        for _, p := range *pq {
            if p.c > 0 {
                tmp = append(tmp, p)
            }
        }
        *pq = tmp
        sort.Slice(*pq, func(i, j int) bool { return (*pq)[i].c > (*pq)[j].c })
    }
    if len(*pq) == 1 {
        ans = append(ans, (*pq)[0].n)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int b : barcodes) cnt.put(b, cnt.getOrDefault(b, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int k : cnt.keySet()) pq.offer(new int[]{cnt.get(k), k});
        List<Integer> ans = new ArrayList<>();
        while (pq.size() > 1) {
            int[] a = pq.poll(), b = pq.poll();
            ans.add(a[1]);
            ans.add(b[1]);
            if (--a[0] > 0) pq.offer(a);
            if (--b[0] > 0) pq.offer(b);
        }
        if (!pq.isEmpty()) ans.add(pq.poll()[1]);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); ++i) res[i] = ans.get(i);
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun rearrangeBarcodes(barcodes: IntArray): IntArray {
        val cnt = mutableMapOf<Int, Int>()
        for (b in barcodes) cnt[b] = cnt.getOrDefault(b, 0) + 1
        val pq = java.util.PriorityQueue<Pair<Int, Int>>(compareByDescending { it.first })
        for ((k, v) in cnt) pq.add(Pair(v, k))
        val ans = mutableListOf<Int>()
        while (pq.size > 1) {
            val (c1, n1) = pq.poll()
            val (c2, n2) = pq.poll()
            ans.add(n1)
            ans.add(n2)
            if (c1 - 1 > 0) pq.add(Pair(c1 - 1, n1))
            if (c2 - 1 > 0) pq.add(Pair(c2 - 1, n2))
        }
        if (pq.isNotEmpty()) ans.add(pq.poll().second)
        return ans.toIntArray()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def rearrangeBarcodes(self, barcodes: list[int]) -> list[int]:
        from collections import Counter
        from heapq import heappush, heappop
        cnt = Counter(barcodes)
        pq = []
        for n, c in cnt.items():
            heappush(pq, (-c, n))
        ans = []
        while len(pq) > 1:
            c1, n1 = heappop(pq)
            c2, n2 = heappop(pq)
            ans.extend([n1, n2])
            if -c1 > 1:
                heappush(pq, (c1 + 1, n1))
            if -c2 > 1:
                heappush(pq, (c2 + 1, n2))
        if pq:
            ans.append(pq[0][1])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn rearrange_barcodes(barcodes: Vec<i32>) -> Vec<i32> {
        use std::collections::{BinaryHeap, HashMap};
        let mut cnt = HashMap::new();
        for &b in &barcodes {
            *cnt.entry(b).or_insert(0) += 1;
        }
        let mut pq = BinaryHeap::new();
        for (&n, &c) in &cnt {
            pq.push((c, n));
        }
        let mut ans = Vec::new();
        while pq.len() > 1 {
            let (c1, n1) = pq.pop().unwrap();
            let (c2, n2) = pq.pop().unwrap();
            ans.push(n1);
            ans.push(n2);
            if c1 > 1 {
                pq.push((c1 - 1, n1));
            }
            if c2 > 1 {
                pq.push((c2 - 1, n2));
            }
        }
        if let Some((_, n)) = pq.pop() {
            ans.push(n);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    rearrangeBarcodes(barcodes: number[]): number[] {
        const cnt = new Map<number, number>();
        for (const b of barcodes) cnt.set(b, (cnt.get(b) || 0) + 1);
        const pq: [number, number][] = [];
        for (const [n, c] of cnt.entries()) pq.push([c, n]);
        pq.sort((a, b) => b[0] - a[0]);
        const ans: number[] = [];
        while (pq.length > 1) {
            let [c1, n1] = pq.shift()!;
            let [c2, n2] = pq.shift()!;
            ans.push(n1, n2);
            if (--c1 > 0) pq.push([c1, n1]);
            if (--c2 > 0) pq.push([c2, n2]);
            pq.sort((a, b) => b[0] - a[0]);
        }
        if (pq.length) ans.push(pq[0][1]);
        return ans;
    }
}