# Smallest Range Covering Elements From K Lists Problem

## Description

LeetCode Problem 632.

You have k lists of sorted integers in non-decreasingorder. 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:

``````1
2
3
4
5
6
Input: nums = [[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].
``````

Example 2:

``````1
2
Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
``````

Example 3:

``````1
2
Input: nums = [[10,10],[11,11]]
Output: [10,11]
``````

Example 4:

``````1
2
Input: nums = [[10],[11]]
Output: [10,11]
``````

Example 5:

``````1
2
Input: nums = [[1],[2],[3],[4],[5],[6],[7]]
Output: [1,7]
``````

Constraints:

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10^5 <= nums[i][j] <= 10^5
• nums[i]is sorted in non-decreasing order.

## Sample C++ Code

``````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
32
33
34
35
36
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
typedef vector<int>::iterator vi;

struct comp {
bool operator()(pair<vi, vi> p1, pair<vi, vi> p2) {
return *p1.first > *p2.first;
}
};

int lo = INT_MAX, hi = INT_MIN;
priority_queue<pair<vi, vi>, vector<pair<vi, vi>>, comp> pq;
for (auto &row : nums) {
lo = min(lo, row[0]);
hi = max(hi, row[0]);
pq.push({row.begin(), row.end()});
}

vector<int> ans = {lo, hi};
while (true) {
auto p = pq.top();
pq.pop();
++p.first;
if (p.first == p.second)
break;
pq.push(p);

lo = *pq.top().first;
hi = max(hi, *p.first);
if (hi - lo < ans[1] - ans[0])
ans = {lo, hi};
}
return ans;
}
};
``````