632. 最小区间 - 贪心算法思路与实现

632. 最小区间

你有 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
• -10^5 <= nums[i][j] <= 10^5
• nums[i] 按非递减顺序排列

思路

题目要求给出若干个非递减序列，算出一个区间 [l,r]，使得每个序列至少有一个数在区间内。

既然题目要求每个序列中至少有一个数在区间内，那么索性先选取各个序列中最小的数也就是各个序列的首元素构成一个集合，此时，集合内的数就会生成一个区间 [l1,r1]，l1 就是所有序列首元素的最小值，r1 就是首元素的最大值。这时候的区间一定满足'每个序列至少有一个数在区间内'的条件，但未必是最小的，之后就要压缩区间。

在压缩区间之前必须明确，在 [l1,r1] 与初始集合的基础上进行压缩，集合内必须保证含有每个序列中的数。而怎么压缩区间就体现了贪心的思想，每次压缩都从集合中弹出最小的数，之后，为了满足'每个序列至少有一个数在区间内'的条件，需要在其所属序列中选择下一个数加入集合，获取新集合的区间对比更新所求区间。

例如：当前从集合中弹出的元素是 nums[i][j]，那么就需要将 nums[i][j+1] 加入集合，假设弹出前集合的区间为 [l1,r1]，l1 为集合中最小元素，r1 为集合中最大元素，[l1,r1] 为当前压缩到的最小区间，即 ans 区间；加入元素后的新集合对应的新区间为 [l2,r2]，此时就要将 ans 与新区间进行对比，如果新区间小于 ans，就更新 ans 为新区间，否则 ans 不动。

为什么每次弹出集合中最小的数，加入其序列中的下一个数？

答：因为题目保证所有序列都为非递减序列，则每次弹出集合中最小的数（也就是 l1），并加入其原序列的下一个数 x，那么 x 一定大于 l1。如果，此时 x 为新集合中最小的数，那么新集合的新区间为 [x,r1] 的长度一定小于原区间长度，又因为 x 是从 l1 的序列中加入集合的，说明弹出、加入的过程不会影响到集合中其他序列的数，也就是一定不会破坏'每个序列至少有一个数在区间内'的条件，所以 [x,r1] 一定是当前满足题意的最小区间，随之更新 ans，从而达到压缩区间的目的；如果此时 x 不为新集合中最小的数，最小的数为 l2，x 可能大于 r1，也可能在 [l2,r1] 之间，此时就要对比新集合的新区间与 ans 的大小，判断是否更新 ans 同样可以压缩区间。即使某个序列中有多个数在区间也无所谓，只要满足'每个序列至少有一个数在区间内'的条件即可。

至此，不断弹出，加入元素，保证集合内元素个数不变，不断在贪心的基础上压缩，直到集合不可再压缩，返回 ans 区间。

代码实现

C++ 实现

class Solution {
public:
    typedef struct node{
        int data;//当前元素数据
        int i;//原序列位置
        int idx;//所在原序列下标
        bool operator < (const node& a)const {
            if (data == a.data) {
                return i < a.i;
            }
            return data < a.data;
        }
    }Node;

    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int> ans;
        if (nums.empty()) {
            return ans;
        }
        set<Node> s;
        for (int i = 0; i < nums.size(); i++) {
            //初始化集合，将每个序列最小数加入集合
            if (nums[i].empty()) {
                continue;
            }
            Node t = { nums[i][0],i,0 };
            s.insert(t);
        }
        if (s.empty()) {
            return ans;
        }
        int l = (*s.begin()).data;
        int r = (*s.rbegin()).data;
        //压缩区间
        while (1) {
            auto it = s.begin();
            int i = (*it).i;
            int idx = (*it).idx;
            if (idx == nums[i].size() - 1) {
                //最小元素弹出后无法再加入元素
                break;//跳出循环，压缩结束
            } else {
                s.erase(s.begin());
                Node t = { nums[i][idx + 1],i,idx + 1 };
                s.insert(t);
                if (((*s.rbegin()).data - (*s.begin()).data) < (r - l)) {
                    //遇到更小的区间，更新
                    r = (*s.rbegin()).data;
                    l = (*s.begin()).data;
                } else if (((*s.rbegin()).data - (*s.begin()).data) == (r - l)) {
                    //同样长度的区间选择字典序更小的，更新
                    if ((*s.begin()).data < l) {
                        r = (*s.rbegin()).data;
                        l = (*s.begin()).data;
                    }
                }
            }
        }
        ans.push_back(l);
        ans.push_back(r);
        return ans;
    }
};

Java 实现

class Solution {
    public class Node implements Comparable<Node> {
        int data;
        int i;
        int idx;
        public Node(int data, int i, int idx) {
            this.data = data;
            this.i = i;
            this.idx = idx;
        }
        public int compareTo(Node a){
            if(this.data==a.data){
                return this.i-a.i;
            }
            return this.data-a.data;
        }
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        int ans[]=new int[2];
        if(nums.size()==0){
            return ans;
        }
        TreeSet<Node> s=new TreeSet<>();
        for (int i = 0; i < nums.size(); i++) {
            if(nums.get(i).size()==0){
                continue;
            }
            Node t=new Node(nums.get(i).get(0),i,0);
            s.add(t);
        }
        if(s.size()==0){
            return ans;
        }
        int l=s.first().data;
        int r=s.last().data;
        while(true){
            Node it=s.first();
            int i=it.i;
            int idx=it.idx;
            if(idx==nums.get(i).size()-1){
                break;
            } else{
                s.remove(s.first());
                Node t=new Node(nums.get(i).get(idx+1),i,idx+1);
                s.add(t);
                int len=s.last().data-s.first().data+1;
                if(len<(r-l+1)){
                    l=s.first().data;
                    r=s.last().data;
                } else if(len==(r-l+1)){
                    if(l>s.getFirst().data){
                        l=s.first().data;
                        r=s.last().data;
                    }
                }
            }
        }
        ans[0]=l;
        ans[1]=r;
        return ans;
    }
}