一、题目

你有 k 个非递减排列的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：
输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释：
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：
输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列

二、代码

class Solution {class Node {// 值大小public int value;// 该数来自哪个数组，记录数组编号public int arrid;// 该数来自数组的哪个下标位置public int index;public Node(int value, int arrid, int index) {this.value = value;this.arrid = arrid;this.index = index;}}// 有序表按照值得递增顺序排序，如果两个值相等，谁的数组编号小，谁就放在前面class NodeComparator implements Comparator {@Overridepublic int compare(Node o1, Node o2) {return o1.value != o2.value ? o1.value - o2.value : o1.arrid - o2.arrid;}}public int[] smallestRange(List> nums) {// 创建有序表TreeSet ansSet = new TreeSet<>(new NodeComparator());// 一开始先将所有数组的第一个数加入到有序表中for (int i = 0; i < nums.size(); i++) {ansSet.add(new Node(nums.get(i).get(0), i, 0));}// 记录有序表最小的节点和最大的节点Node start = ansSet.first();Node end = ansSet.last();// 记录当前找到的符合条件的区间最窄的区间左右边界int min = start.value;int max = end.value;// 当我们想要删掉一个数据时，发现这个数据所在的数组已经没有别的数可以用来补充到有序表了，那么整个流程就不用再继续了，以为后面就无法满足每一个数组至少有一个数在有序表了while (start.index != nums.get(start.arrid).size() - 1) {// 弹出有序表中最小的数ansSet.pollFirst();// 将弹出的数所在数组的下一个位置的数加入到有序表中，保证这个数组有一个数在有序表中ansSet.add(new Node(nums.get(start.arrid).get(start.index + 1), start.arrid, start.index + 1));// 记录此时有序表的区间范围start = ansSet.first();end = ansSet.last(); // 如果此时的区间比之前记录的更窄，就更新答案if (end.value - start.value < max - min) {max = end.value;min = start.value;// 如果此时的区间等于之前记录的区间，就看是否当前的区间起始数是不是比以前的起始数小，如果小就更新答案} else if (end.value - start.value == max - min) {if (start.value < min) {max = end.value;min = start.value;}}}// 返回符合条件的最窄区间return new int[] {min, max};}
}