package interview;

import com.list.listProblems.IsHuiWenList;
import sun.reflect.generics.tree.Tree;

import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

public class SmallestRange {

 public static class Node {
 private int value;
 private int arrIndex;
 private int ownIndex;

 public Node(int value, int arrIndex, int ownIndex) {
 this.value = value;
 this.arrIndex = arrIndex;
 this.ownIndex = ownIndex;
 }
 }

 public static class NodeComparator implements Comparator<Node> {

 @Override
 public int compare(Node o1, Node o2) {
 return o1.value != o2.value ? o1.value - o2.value : o1.arrIndex - o2.arrIndex;
 }
 }

 public int[] smallestRange(List<List<Integer>> nums) {
 int N = nums.size();
 TreeSet<Node> treeSet = new TreeSet<>(new NodeComparator());
 // TreeSet<Node> treeSet = new TreeSet<Node>((o1, o2) -> {
 // return o1.value != o2.value ? o1.value - o2.value : o1.arrIndex - o2.arrIndex;
 // });
 for (int i = 0; i < N; i++) {
 treeSet.add(new Node(nums.get(i).get(0), i, 0));
 }
 // boolean flag = false;
 int r = Integer.MAX_VALUE;
 int a = 0;
 int b = 0;
 while (treeSet.size() == N) {
 Node first = treeSet.first();
 Node last = treeSet.last();
 // if (!flag || last.value - first.value < b - a) {
 // flag = true;
 // b = last.value;
 // a = first.value;
 // }
 if (last.value - first.value < r) {
 r = last.value - first.value;
 b = last.value;
 a = first.value;
 }
 Node min = treeSet.pollFirst();
 int arrIndex = min.arrIndex;
 int ownIndex = min.ownIndex;
 if (ownIndex <= nums.get(arrIndex).size() - 2) {
 treeSet.add(new Node(nums.get(arrIndex).get(ownIndex + 1), arrIndex, ownIndex + 1));
 }
 }
 return new int[]{a, b};
 }
}