[Leetcode] Smallest Range

This is a smart use of heap.

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.

class Solution(object):
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        h = []
        max_v = -10**5 - 1
        min_v = 10**5 + 1
        for i, num in enumerate(nums):
            h.append([num[0], i, 0])
            if max_v < num[0]: max_v = num[0]
            if min_v > num[0]: min_v = num[0]
        res = [min_v, max_v]
        
        heapq.heapify(h)
        
        while True:
            v, list_index, element_index = heapq.heappop(h)
            if element_index == len(nums[list_index]) - 1:
                return res
            heapq.heappush(h, [nums[list_index][element_index+1], list_index, element_index+1]) 
            if nums[list_index][element_index+1] > max_v:
                max_v = nums[list_index][element_index+1]
            if max_v - h[0][0] < res[1] - res[0]:
                res = [h[0][0], max_v]