632. Smallest Range Covering Elements from K Lists

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 range `[c, d]` if `b - a < d - c` or `a < c` if `b - a == d - c`.

Example 1:

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

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

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

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

632. Smallest Range Covering Elements from K Lists
``````struct Solution;

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
let n = nums.len();
let mut queue: BinaryHeap<(Reverse<i32>, usize, usize)> = BinaryHeap::new();
let mut left = std::i32::MAX;
let mut right = std::i32::MIN;
for i in 0..n {
let x = nums[i][0];
left = left.min(x);
right = right.max(x);
queue.push((Reverse(x), i, 1));
}
let mut min = (right - left, (left, right));
while let Some((Reverse(_), i, j)) = queue.pop() {
if j == nums[i].len() {
break;
} else {
let x = nums[i][j];
right = right.max(x);
queue.push((Reverse(x), i, j + 1));
if let Some(&(Reverse(y), _, _)) = queue.peek() {
left = left.max(y);
}
let r = (right - left, (left, right));
if r < min {
min = r;
}
}
}
vec![(min.1).0, (min.1).1]
}
}

#[test]
fn test() {
let nums = vec_vec_i32![[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
let res = vec![20, 24];
assert_eq!(Solution::smallest_range(nums), res);
}
``````