Задача: 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) {
    $count = array_count_values($barcodes);
    $maxHeap = new SplPriorityQueue();
    foreach ($count as $barcode => $freq) {
        $maxHeap->insert($barcode, $freq);
    }

    $result = [];
    $prevFreq = 0;
    $prevBarcode = null;

    while (!$maxHeap->isEmpty()) {
        $barcode = $maxHeap->extract();
        $freq = $count[$barcode];
        $result[] = $barcode;
        if ($prevFreq > 0) {
            $maxHeap->insert($prevBarcode, $prevFreq);
        }
        $prevFreq = $freq - 1;
        $prevBarcode = $barcode;
    }

    return $result;
}

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