LeetCode 757. Set Intersection Size At Least Two题目解析

Description

An integer interval [a, b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b.

Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has size at least 2.

Example 1:

Input: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
Output: 3
Explanation:Consider the set S = {2, 3, 4}.  For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.

Example 2:

Input: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
Output: 5
Explanation:An example of a minimum sized set is {1, 2, 3, 4, 5}.

Note:

  1. intervals will have length in range [1, 3000].

  2. intervals[i] will have length 2, representing some integer interval.

  3. intervals[i][j] will be an integer in [0, 10^8].

题目复述

一个区间[a, b]表示a到b的所有整数(包括a, b),找出最小数量的整数集合S,使得S和每个区间相交的整数个数大于等于2,返回S集合中整数的个数。例如对于区间[1, 3]、[2, 4],S = {2, 3},即答案为2。

题目解析

考虑使用贪心法来解决此问题,我们首先对区间排序,排序的时候区间右端点小的排前面,区间右端点一样的情况下区间左端点小的排前面,排序后优先选择区间最后两个数加入集合即可。例如对于样例[1, 3], [1, 4], [2, 5], [3, 5],排序后为[1, 3], [1, 4], [2, 5], [3, 5],逐个满足的操作如下:

初始S = {}

S和[1, 3]交集个数为0,将{2, 3}加入,S = {2, 3}

S和[1, 4]交集个数为1,将{4}加入,S = {2, 3, 4}

……

class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        if(a[1] != b[1]) return a[1] < b[1];
        else return a[0] > b[0];
    }
    //获取区间和S的交集个数
    int get_num(vector<int> &interval, vector<int> &res) { 
        int num = 0;
        for(int i=0; i<res.size(); i++)
            if(res[i]>=interval[0] && res[i]<=interval[1])
                num++;
        return num;
    }
    
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int flog = 1;
        vector<int> res;
        for(int i=0; i<intervals.size(); i++) {
            if(i == 0) {
                res.push_back(intervals[i][1]);
                res.push_back(intervals[i][1]-1);
            }else {
                int num = get_num(intervals[i], res);
                if(num == 0) {
                    res.push_back(intervals[i][1]);
                    res.push_back(intervals[i][1]-1);
                }else if(num == 1) 
                    res.push_back(intervals[i][1]);
            }
        }
        
        return res.size();
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注