---

前言

你有 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

有序表
非常方便的查到所有数字最小值，也可以非常方便的查到所有数字的最大直
每个数组中的第一个数加入有序表, 取出最大值跟最小值,可以找到一个区间
这个区间一定每个数组都有一个数落在这个区间上
然后删除最小值,把这个最小值来自数组的下一个值加入有序表,排序后重新取出最小值跟最大值
构成一个新的区间,跟之前的区间比较是否更优
当你有一个数组耗尽了,不用再继续了，你找到的最窄区间出来了

每个数组的第一个数进入有序表

7进入有序表,把1淘汰,最小区间更新
最后把所有数字都遍历一遍,得到最小的区间

代码

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};
    }
}
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
41
42
43