8.28 - hard - 112

632. Smallest Range

竞赛时候手写出来的题目，就不重新做了

import heapq
class Solution(object):
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        heap = []
        index  = [0 for _ in range(len(nums))]
        
        for i in range(len(nums)):
            if not nums[i]:
                return []
            heapq.heappush(heap, (nums[i][0], i))
        
        cur_range = max(heap)[0] - min(heap)[0]
        res = [min(heap)[0], max(heap)[0]]
        cur_max = res[1]
        while True:
            _, i = heap[0]
            if index[i] == len(nums[i]) - 1:
                return res
            else:
                heapq.heappop(heap)
            index[i] += 1
            heapq.heappush(heap, (nums[i][index[i]], i))
            cur_min, _ = heap[0]
            if nums[i][index[i]] > cur_max:
                cur_max = nums[i][index[i]]
            if cur_range > cur_max - cur_min:
                cur_range = cur_max - cur_min
                res = [cur_min, cur_max]