README.md

1054. Distant Barcodes

In a warehouse, there is a row of barcodes, where the ith 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: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: barcodes = [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,1,2,1,2]

Constraints:

• 1 <= barcodes.length <= 10000
• 1 <= barcodes[i] <= 10000

Solutions (Rust)

1. Heap

use std::collections::BinaryHeap;
use std::collections::HashMap;

impl Solution {
    pub fn rearrange_barcodes(barcodes: Vec<i32>) -> Vec<i32> {
        let mut count = HashMap::new();
        let mut heap = BinaryHeap::new();
        let mut ret = vec![];

        for bar in barcodes {
            *count.entry(bar).or_insert(0) += 1;
        }
        for (k, v) in count.into_iter() {
            heap.push((v, k));
        }

        while let Some(mut max0) = heap.pop() {
            ret.push(max0.1);
            max0.0 -= 1;
            if let Some(mut max1) = heap.pop() {
                ret.push(max1.1);
                max1.0 -= 1;
                if max1.0 > 0 {
                    heap.push(max1);
                }
            }
            if max0.0 > 0 {
                heap.push(max0);
            }
        }

        ret
    }
}