package com.fishercoder.solutions;

import java.util.List;
import java.util.PriorityQueue;

/**
 * 632. Smallest Range
 *
 * 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:
 The given list may contain duplicates, so ascending order means >= here.
 1 <= k <= 3500
 -105 <= value of elements <= 105.
 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.

 */
public class _632 {
    /**
     * reference: https://discuss.leetcode.com/topic/94445/java-code-using-priorityqueue-similar-to-merge-k-array/2
     */
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(nums.size(), (a, b) -> a[0] - b[0]);
        /**int[] array consists of three numbers: value; which list in nums; index of value in this list*/

        int max = nums.get(0).get(0);
        for (int i = 0; i < nums.size(); i++) {
            minHeap.offer(new int[]{nums.get(i).get(0), i, 0});
            max = Math.max(max, nums.get(i).get(0));
        }
        int minRange = Integer.MAX_VALUE;
        int start = -1;
        while (minHeap.size() == nums.size()) {
            int[] curr = minHeap.poll();
            if (max - curr[0] < minRange) {
                minRange = max - curr[0];
                start = curr[0];
            }
            if (curr[2] + 1 < nums.get(curr[1]).size()) {
                curr[0] = nums.get(curr[1]).get(curr[2] + 1);
                curr[2]++;
                minHeap.offer(curr);
                max = Math.max(max, curr[0]);
            }
        }
        return new int[]{start, start + minRange};
    }
}

@@ -917,20 +917,64 @@
 2 %7B%0A    
-/**%0A
+public static class Solution1 %7B%0A        /**%0A    
      * r
@@ -1090,15 +1090,23 @@
     
+    
 */%0A    
+ 
+   
 publ
@@ -1152,24 +1152,28 @@
 r%3E%3E nums) %7B%0A
+    
         Prio
@@ -1264,16 +1264,20 @@
         
+  
+  
 /**int%5B%5D
@@ -1372,24 +1372,28 @@
 */%0A%0A        
+    
 int max = nu
@@ -1410,16 +1410,20 @@
 get(0);%0A
+    
         
@@ -1466,32 +1466,36 @@
 ) %7B%0A            
+    
 minHeap.offer(ne
@@ -1534,32 +1534,36 @@
 %7D);%0A            
+    
 max = Math.max(m
@@ -1587,34 +1587,42 @@
 et(0));%0A        
+ 
-%7D%0A
+   %7D%0A    
         int minR
@@ -1651,24 +1651,28 @@
 UE;%0A        
+   
+ 
 int start = 
@@ -1675,16 +1675,20 @@
 t = -1;%0A
+    
         
@@ -1739,16 +1739,20 @@
         
+    
 int%5B%5D cu
@@ -1780,24 +1780,28 @@
             
+ 
+   
 if (max - cu
@@ -1836,16 +1836,20 @@
         
+    
 minRange
@@ -1882,16 +1882,20 @@
         
+   
+ 
 start = 
@@ -1907,34 +1907,42 @@
 0%5D;%0A            
-%7D%0A
+    %7D%0A    
             if (
@@ -1995,24 +1995,28 @@
             
+    
 curr%5B0%5D = nu
@@ -2061,24 +2061,28 @@
             
+    
 curr%5B2%5D++;%0A 
@@ -2088,32 +2088,36 @@
                 
+  
+  
 minHeap.offer(cu
@@ -2121,16 +2121,20 @@
 (curr);%0A
+    
         
@@ -2175,34 +2175,42 @@
 %5D);%0A            
+   
+ 
 %7D%0A
+    
         %7D%0A      
@@ -2195,32 +2195,36 @@
 %7D%0A            %7D%0A
+    
         return n
@@ -2258,16 +2258,26 @@
 Range%7D;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 632