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

😎 Решение:

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int barcode : barcodes) {
            count.put(barcode, count.getOrDefault(barcode, 0) + 1);
        }

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            maxHeap.add(new int[]{entry.getValue(), entry.getKey()});
        }

        int prevFreq = 0, prevBarcode = -1;
        int[] result = new int[barcodes.length];
        int index = 0;

        while (!maxHeap.isEmpty()) {
            int[] entry = maxHeap.poll();
            int freq = entry[0], barcode = entry[1];
            result[index++] = barcode;
            if (prevFreq > 0) {
                maxHeap.add(new int[]{prevFreq, prevBarcode});
            }
            prevFreq = freq - 1;
            prevBarcode = barcode;
        }

        return result;
    }
}

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