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