Задача: 1054. Distant Barcodes
Сложность: medium

На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.

Пример:

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

👨‍💻 Алгоритм:

1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.

2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.

3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

func rearrangeBarcodes(_ barcodes: [Int]) -> [Int] {
    let count = Dictionary(barcodes.map { ($0, 1) }, uniquingKeysWith: +)
    var maxHeap = count.map { (-$0.value, $0.key) }
    maxHeap.sort(by: <)

    var prevFreq = 0
    var prevBarcode = 0
    var result = [Int]()
    
    while !maxHeap.isEmpty {
        let (freq, barcode) = maxHeap.removeLast()
        result.append(barcode)
        if prevFreq < 0 {
            maxHeap.append((prevFreq, prevBarcode))
            maxHeap.sort(by: <)
        }
        
        prevFreq = freq + 1
        prevBarcode = barcode
    }
    
    return result
}

Ставь 👍 и забирай 📚 Базу знаний