/
632.py
31 lines (31 loc) · 888 Bytes
/
632.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
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
v = list()
for i in range(len(nums)):
for num in nums[i]:
v.append((num, i))
v.sort()
l, r, n = 0, 0, len(v)
d = collections.defaultdict(int)
k = len(nums)
cnt = 0
res = [0, 0]
diff = float('inf')
while r < n:
if d[v[r][1]] == 0:
cnt += 1
d[v[r][1]] += 1
while l <= r and cnt == k:
if v[r][0] - v[l][0] < diff:
diff = v[r][0] - v[l][0]
res = [v[l][0], v[r][0]]
d[v[l][1]] -= 1
if d[v[l][1]] == 0:
del d[v[l][1]]
cnt -= 1
l += 1
r += 1
return res