632. Smallest Range Covering Elements from K Lists

class Solution:
    def smallestRange(self, A: List[List[int]]) -> List[int]:
        """ tc O(NlgK)  sc O(K)
                   PQ : (diff, i,j)
        main idea: find res: max-min so that res is smallest =>  get min,max as close as possible 
        1. put smallest val of each row into pq.   tuple (val, i,0) i:row number,  0:right most 
        2. get max val in each row's first , set as global right.  set defaut res : max inteval of right - left  
        3. pop smallest v and compare with optimal res 
        4. check if next right position has reaches to the end, if yes, return res directly 
        5. otherwise, keep updating right value with next right position
        6. use next right val as left point, push updated tuple into pq 
        
        ???  why we can terminate when next right pos reaches current row's (with local smallest left val) end ?  => because we need a range covering all the rows, if one row has reached the end, there is no other range will suffice  
        ???  how does this prove we will get min(right-left)??? 
        """
        res = 1e-5,1e5#float('inf')
        pq = [] 
        right = 0 
        for i,row in enumerate(A):  # KlgK
            # push (left, row #, current_idex)
            heappush(pq,(row[0],i,0))
            right = max(right,row[0])
        
        while pq: 
            left,i,j = heappop(pq)  #NlgK  N: len(A[i])
            if right-left < res[1]-res[0]:
                res = left,right # update res 
            # move min forward to try to find closer right 
                 # termination condition: reach end 
            if j+1 == len(A[i]):
                return res 
            v = A[i][j+1] # potential right
            right = max(right,v)
            heappush(pq,(v,i,j+1))