Smallest Range Covering Elements from K Lists

Intuition

Solution

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heap = []
        max_v = nums[0][0]
        for i in range(len(nums)):
            max_v = max(nums[i][0], max_v)
            heapq.heappush(heap, [nums[i][0], i, 0])
        ans = [heap[0][0], max_v]
        diff = max_v - heap[0][0]
        while True:
            v, i, j = heapq.heappop(heap)
            if j + 1 >= len(nums[i]):
                break
            heapq.heappush(heap, [nums[i][j+1], i, j + 1])
            max_v = max(max_v, nums[i][j+1])
            if diff > max_v - heap[0][0]:
                diff = max_v - heap[0][0]
                ans = [heap[0][0], max_v]
        return ans