【LeetCode】最小区间 [H]（贪心）

632. 最小区间 - 力扣（LeetCode）

一、题目

你有 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 {
        @Override
        public 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};
    }
}

三、解题思路 

有序表能非常方便地查到所有数字最小值，也可以非常方便的查到所有数字的最大值。

将每个数组中的第一个数加入有序表，取出最大值和最小值，可以找到一个区间。

这个区间一定每个数组都有一个数落在这个区间上，

然后删除最小值，把这个最小值来自数组的下一个值加入有序表，排序后重新取出最小值跟最大值，

构成一个新的区间，跟之前的区间比较是否更优。

当我们想要删掉一个数据时，发现这个数据所在的数组已经没有别的数可以用来补充到有序表了，那么整个流程就不用再继续了，这时就找到符合要求的最窄区间了。整个流程中我们可以保证在有序表的范围中每一个数据集合都至少有一个数在这个有序表所在的范围中。

所以整个流程就相当于每一个数产生答案的时候都是某一个数字如果作为连续区间的开头往右怎么样最经济,

这样你就把所有答案都穷举了一遍，然后从其中找最优解。而且整个流程一定就可以保证每一个数组只会有一个数在有序表中，可以尽最大可能保证区间范围最窄。