-
Notifications
You must be signed in to change notification settings - Fork 0
/
smallestRange.py
33 lines (27 loc) · 1 KB
/
smallestRange.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
You have k lists of sorted integers in ascending 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 range [c,d] if b-a < d-c or a < c if b-a == d-c.
"""
import heapq
import sys
def smallestRange(nums):
indicies = [0]*len(nums)
minHeap = []
minRange = -sys.maxint - 1
maxRange = sys.maxint
max_value = -sys.maxint - 1
for i in range(len(nums)):
heapq.heappush(minHeap, (nums[i][0], i))
max_value = max(max_value, nums[i][0])
while True:
min_ = minHeap[0][1]
min_value = minHeap[0][0]
if maxRange - minRange > max_value - min_value:
maxRange = max_value
minRange = min_value
indicies[min_] += 1
if (indicies[min_] >= len(nums[min_])):
break
heapq.heapreplace(minHeap, (nums[min_][indicies[min_]], min_))
max_value = max(max_value, nums[min_][indicies[min_]])
return (minRange, maxRange)