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 == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i] is sorted in non-decreasing order.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);
}