# 632. Smallest Range Covering Elements from K Lists 最小区间

## # 题目描述：

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`.

Example 1:

``````Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
``````

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.
4. For Java users, please note that the input type has been changed to `List<List<Integer>>`. And after you reset the code template, you'll see this point.

## # 解题方法

``````class Solution(object):
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
``````

http://www.cnblogs.com/grandyang/p/7200016.html

## # 日期

2018 年 10 月 3 日 —— 玩游戏导致没睡好，脑子是浆糊。