LeetCode [632] Smallest Range Covering Elements from K Lists

632. Smallest Range Covering Elements from K Lists

Hard

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.

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 37 38 39 40

class Solution { int[] minRange = new int[2]; int l, r, n; void update(){ if(r-l<minRange[1]-minRange[0]){ minRange[0] = l; minRange[1] = r; } } public int[] smallestRange(List<List<Integer>> nums) { n = nums.size(); l = Integer.MAX_VALUE; r = Integer.MIN_VALUE; PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(Integer.compare(a[0], b[0])));//value, col, row for(int i=0; i<n; ++i){ int v = nums.get(i).get(0); pq.add(new int[]{v, i, 0}); l = Math.min(l, v); r = Math.max(r, v); } minRange[0] = l; minRange[1] = r; while(true){ int[] top = pq.poll(); int col = top[1], row = top[2]; if(row == nums.get(col).size()-1) break;//the min value reach the last of the list int v = nums.get(col).get(row+1); pq.add(new int[]{v, col, row+1}); l = pq.peek()[0]; r = Math.max(r, v); update(); } return minRange; } }