1
from typing import List
2
import heapq
3

4

5
class Solution:
6
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
7
        heap = [(row[0], i, 0) for i, row in enumerate(nums)]
8
        heapq.heapify(heap)
9
        ans = [-(10**9), 10**9]
10
        right = max(row[0] for row in nums)
11
        while heap:
12
            left, row, col = heapq.heappop(heap)
13
            if right - left < ans[1] - ans[0]:
14
                ans = [left, right]
15
            if col + 1 == len(nums[row]):
16
                return ans
17
            right = max(right, nums[row][col + 1])
18
            heapq.heappush(heap, (nums[row][col + 1], row, col + 1))
19

20

21
# Tests:
22
if __name__ == "__main__":
23
    s = Solution()
24
    # test case 1
25
    output1 = s.smallestRange([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]])
26
    expected_output1 = [20, 24]
27
    assert (
28
        output1 == expected_output1
29
    ), f"Expected {expected_output1}, but got {output1}"
30
    # test case 2
31
    output2 = s.smallestRange([[1, 2, 3], [1, 2, 3], [1, 2, 3]])
32
    expected_output2 = [1, 1]
33
    assert (
34
        output2 == expected_output2
35
    ), f"Expected {expected_output2}, but got {output2}"
36
    print("All tests passed!")