632. Minimum interval

---

前言

你有 k 个 非递减排列 的整数列表.找到一个 最小 区间,使得 k 个列表中的每个列表至少有一个数包含在其中.

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c,则区间 [a,b] 比 [c,d] 小.

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.

解题思路

有序表
It is very convenient to find the minimum value of all numbers,It is also very convenient to find the maximum straight of all numbers
The first number in each array is added to the sorted list, Get the maximum and minimum values,An interval can be found
This interval must have a number in each array that falls on this interval
然后删除最小值,Adds the next value with this minimum value from the array to the sorted list,After sorting, the minimum and maximum values ​​are retrieved
form a new interval,跟之前的区间比较是否更优
When you have an array exhausted,不用再继续了,The narrowest interval you found is out

The first number of each array goes into the sorted list

7enter the ordered list,把1淘汰,Minimum interval update
Finally iterate over all the numbers,get the smallest interval

代码

class Solution {
    
    public class Node{
    
        public int value;
        public int arrid;
        public int index;
        public Node(int v,int ai,int i){
    
            value=v;
            arrid=ai;
            index=i;
        }
    }
    public class NodeComparator implements Comparator<Node>{
    
        public int compare(Node o1,Node o2){
    
            return o1.value!=o2.value?o1.value-o2.value:o1.arrid-o2.arrid;
        }
    }
    public int[] smallestRange(List<List<Integer>> nums) {
    
        int N=nums.size();
        TreeSet<Node> orderSet=new TreeSet<>(new NodeComparator());
        for(int i=0;i<N;i++){
    
            orderSet.add(new Node(nums.get(i).get(0),i,0));
        }
        boolean set=false;
        int a=0;
        int b=0;
        while(orderSet.size()==N){
    
            Node min=orderSet.first();
            Node max=orderSet.last();
            if(!set||(max.value-min.value<b-a)){
    
                set=true;
                a=min.value;
                b=max.value;
            }
            min=orderSet.pollFirst();
            int arrid=min.arrid;
            int index=min.index+1;
            if(index!=nums.get(arrid).size()){
    
                orderSet.add(new Node(nums.get(arrid).get(index),arrid,index));
            }
        }
        return new int[]{
    a,b};
    }
}