Задача: 632. Smallest Range Covering Elements from K Lists
Сложность: hard

У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.

Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

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

1⃣Инициализация и сбор всех начальных элементов: Создайте массив для хранения текущих индексов каждого списка и используйте минимальную кучу для отслеживания текущих минимальных элементов из каждого списка.

2⃣Нахождение минимального диапазона: Используйте кучу для извлечения минимального элемента и обновления текущего диапазона. Обновляйте максимальный элемент в текущем диапазоне при добавлении новых элементов.

3⃣Проверка и обновление диапазона: Продолжайте обновлять кучу и диапазон, пока возможно. Завершите, когда один из списков исчерпан.

😎 Решение:

import java.util.PriorityQueue;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Element> minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);
        int maxValue = Integer.MIN_VALUE;

        for (int i = 0; i < nums.size(); i++) {
            int value = nums.get(i).get(0);
            minHeap.add(new Element(value, i, 0));
            maxValue = Math.max(maxValue, value);
        }

        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;

        while (minHeap.size() == nums.size()) {
            Element minElement = minHeap.poll();
            if (maxValue - minElement.value < rangeEnd - rangeStart) {
                rangeStart = minElement.value;
                rangeEnd = maxValue;
            }

            if (minElement.col + 1 < nums.get(minElement.row).size()) {
                int value = nums.get(minElement.row).get(minElement.col + 1);
                minHeap.add(new Element(value, minElement.row, minElement.col + 1));
                maxValue = Math.max(maxValue, value);
            }
        }

        return new int[]{rangeStart, rangeEnd};
    }
}

class Element {
    int value, row, col;
    Element(int value, int row, int col) {
        this.value = value;
        this.row = row;
        this.col = col;
    }
}

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