package leetcode;

import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;

/**
 * https://leetcode.com/problems/smallest-range/
 */
public class Problem632 {
    public int[] smallestRange(List<List<Integer>> nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.size(); i++) {
            List<Integer> list = nums.get(i);
            for (int j = 0; j < list.size(); j++) {
                int val = list.get(j);
                boolean found = true;
                for (int k = 0; k < nums.size(); k++) {
                    int lo = nums.get(k).get(0);
                    int hi = nums.get(k).get(nums.get(k).size() - 1);
                    if (lo > val || val > hi) {
                        found = false;
                    }
                }
                if (found) {
                    set.add(val);
                }
            }
        }
        int[] result = new int[2];
        int i = 0;
        int prev = 0;
        int min = Integer.MAX_VALUE;
        for (int val : set) {
            if (i == 0) {
                prev = val;
            } else {
                int diff = val - prev;
                if (diff < min) {
                    diff = min;
                    result[0] = prev;
                    result[1] = val;
                }
                prev = val;
            }
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
        Problem632 prob = new Problem632();
        System.out.println(Arrays.toString(prob.smallestRange(Arrays.asList(
            Arrays.asList(4, 10, 15, 24, 26),
            Arrays.asList(0, 9, 12, 20),
            Arrays.asList(5, 18, 22, 30)
        )))); // [20,24]
    }
}

@@ -77,23 +77,29 @@
 va.util.
-TreeSet
+PriorityQueue
 ;%0A%0A/**%0A 
@@ -247,139 +247,292 @@
     
-TreeSet%3CInteger%3E set = new TreeSet%3C%3E();%0A        for (int i = 0; i %3C nums.size(); i++) %7B%0A            List%3CInteger%3E list = nums.get(i
+int minx = 0;%0A        int miny = Integer.MAX_VALUE;%0A        int max = Integer.MIN_VALUE;%0A        int%5B%5D next = new int%5Bnums.size()%5D;%0A        boolean flag = true;%0A        PriorityQueue%3CInteger%3E minQueue = new PriorityQueue%3C%3E((i, j) -%3E nums.get(i).get(next%5Bi%5D) - nums.get(j).get(next%5Bj%5D)
 );%0A 
@@ -530,36 +530,32 @@
 t%5Bj%5D));%0A        
-    
 for (int j = 0; 
@@ -551,23 +551,23 @@
 int 
-j
+i
  = 0; 
-j %3C list
+i %3C nums
 .siz
@@ -571,17 +571,17 @@
 size(); 
-j
+i
 ++) %7B%0A  
@@ -594,71 +594,78 @@
     
-    int val = list.get(j);%0A                boolean found = true
+minQueue.offer(i);%0A            max = Math.max(max, nums.get(i).get(0))
 ;%0A  
@@ -662,32 +662,34 @@
 et(0));%0A        
+%7D%0A
         for (int
@@ -693,16 +693,16 @@
 int 
-k
+i
  = 0; 
-k
+i
  %3C n
@@ -715,11 +715,19 @@
 ze()
+ && flag
 ; 
-k
+i
 ++) 
@@ -744,24 +744,27 @@
     
-        int lo =
+for (int j = 0; j %3C
  num
@@ -773,23 +773,34 @@
 get(
-k).get(0);%0A    
+i).size() && flag; j++) %7B%0A
     
@@ -819,579 +819,383 @@
 int 
-h
+min
 i = 
-nums.get(k).get(nums.get(k).size() - 1);%0A                    if (lo %3E val %7C%7C val %3E hi) %7B%0A                        found = false;%0A                    %7D%0A                %7D%0A                if (found) %7B%0A                    set.add(val);%0A                %7D%0A            %7D%0A        %7D%0A        int%5B%5D result = new int%5B2%5D;%0A        int i = 0;%0A        int prev = 0;%0A        int min = Integer.MAX_VALUE;%0A        for (int val : set) %7B%0A            if (i == 0) %7B%0A                prev = val;%0A            %7D else %7B%0A                int diff = val - prev;%0A                if (diff %3C min) %7B%0A  
+minQueue.poll();%0A                if (miny - minx %3E max - nums.get(mini).get(next%5Bmini%5D)) %7B%0A                    minx = nums.get(mini).get(next%5Bmini%5D);%0A                    miny = max;%0A                %7D%0A                next%5Bmini%5D++;%0A                if (next%5Bmini%5D == nums.get(mini).size()) %7B%0A                    flag = false;%0A                    break;%0A                %7D%0A
     
@@ -1210,20 +1210,28 @@
     
-  diff = 
+minQueue.offer(
 min
+i)
 ;%0A  
@@ -1248,143 +1248,74 @@
     
-    result%5B0%5D = prev;%0A                    result%5B1%5D = val;%0A                %7D%0A                prev = val;%0A            %7D%0A            i++;
+max = Math.max(max, nums.get(mini).get(next%5Bmini%5D));%0A            %7D
 %0A   
@@ -1340,14 +1340,29 @@
 urn 
-result
+new int%5B%5D%7Bminx, miny%7D
 ;%0A  

Update problem 632