Задача: 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⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

function rearrangeBarcodes(barcodes) {
    const count = new Map();
    for (const barcode of barcodes) {
        count.set(barcode, (count.get(barcode) || 0) + 1);
    }

    const maxHeap = [];
    for (const [barcode, freq] of count) {
        maxHeap.push([-freq, barcode]);
    }
    maxHeap.sort((a, b) => a[0] - b[0]);

    const result = [];
    let prevFreq = 0;
    let prevBarcode = null;

    while (maxHeap.length) {
        const [freq, barcode] = maxHeap.pop();
        result.push(barcode);
        if (prevFreq < 0) {
            maxHeap.push([prevFreq, prevBarcode]);
            maxHeap.sort((a, b) => a[0] - b[0]);
        }
        prevFreq = freq + 1;
        prevBarcode = barcode;
    }

    return result;
}

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