diff options
Diffstat (limited to 'smallest_range_convering_elem_k.py')
-rw-r--r-- | smallest_range_convering_elem_k.py | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/smallest_range_convering_elem_k.py b/smallest_range_convering_elem_k.py new file mode 100644 index 0000000..35b0e77 --- /dev/null +++ b/smallest_range_convering_elem_k.py @@ -0,0 +1,37 @@ +# 632. Smallest Range Covering Elements from K Lists +import heapq + +""" +you have 'k' lists of sorted integers in non decreasing order. find the +smallest range that includes at least one number from each of the 'k' lists. +we define the range '[a, b]' is smaller than the range '[c, d]' if 'b - a < d +- c' or 'a < c' if 'b - a == d - c' +""" + + +class Solution(object): + def smallestRange(self, nums): + """ + :type nums: List[List[int]] + :rtype: List[int] + """ + pq = [(row[0], i, 0) for i, row in enumerate(nums)] + ans = -1e9, 1e9 + right = max(row[0] for row in nums) + while pq: + left, i, j = heapq.heappop(pq) + if right - left < ans[1] - ans[0]: + ans = left, right + if j + 1 == len(nums[i]): + return ans + v = nums[i][j + 1] + right = max(right, v) + heapq.heappush(pq, (v, i, j + 1)) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.smallestRange(nums=[[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]) + ) + print(obj.smallestRange(nums=[[1, 2, 3], [1, 2, 3], [1, 2, 3]])) |