#ЛитКод
Задача: 632. Smallest Range Covering Elements from K Lists

У вас есть 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

data class Element(val value: Int, val row: Int, val col: Int)

class Solution {
    fun smallestRange(nums: List<List<Int>>): IntArray {
        val minHeap = PriorityQueue<Element> { a, b -> a.value - b.value }
        var maxValue = Int.MIN_VALUE

        for (i in nums.indices) {
            minHeap.add(Element(nums[i][0], i, 0))
            maxValue = maxOf(maxValue, nums[i][0])
        }

        var rangeStart = 0
        var rangeEnd = Int.MAX_VALUE

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

            if (minElement.col + 1 < nums[minElement.row].size) {
                val value = nums[minElement.row][minElement.col + 1]
                minHeap.add(Element(value, minElement.row, minElement.col + 1))
                maxValue = maxOf(maxValue, value)
            }
        }

        return intArrayOf(rangeStart, rangeEnd)
    }
}

👉Новости 👉Платформа