力扣-设置交集大小至少为2

ohye / 2023-07-29 / 原文

1.问题描述

一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]

输出: 3

解释:

考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。

且这是S最小的情况，故我们输出3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]

输出: 5

解释:

最小的集合S = {1, 2, 3, 4, 5}.

2.输入说明

首先输入intervals 的区间个数m（范围为[1, 3000]），

然后输入m行，每行2个数字（ [0, 10^8]范围内的整数），表示区间的左、右边界。

3.输出说明

输出一个整数。

4.范例

输入：

4
1 2
2 3
2 4
4 5

输出：

5.思路

（1）根据题设要求，S可以不是连续段

（2）对intervals（后面简称ins）进行排序，按左区间从小到大排序，当左区间一样时，按右区间从大到小排序，其原因：假设我们有一个ins = [[2,3]，[3,4]，[5,10]，[5,8]] (已排好序), 只要我们满足了和[5,8]的交集大于等于2，则对于[5,10]（左区间相同，右区间降序，保证在左区间相同的情况下让区间范围最小的在最右边）这个区间来说，必定是满足交集大于等于2的，因为小区间满足，大区间必然满足，反过来不一定。

（3）在左区间相同的情况下，我们取最小区间的两个元素就可以满足所有左区间相同的区间。因此我们贪心的取interval[n-1][0]和interval[n-1][0] + 1做为开始的两个集合元素，设初始两个元素为ls和rs，则 ls = ins[n - 1][0]，rs = ins[n - 1][0] + 1。

设选取的两个数分别为ls 和rs，此时的答案为2，接下来我们遍历后续的所有区间，对于当前区间的起点xi和终点yi，根据排序有 xi<= ls ，有以下几种情况：

若yi >= rs，则是一个大区间，一定满足交集为2的情况；
若yi < ls，则一定没有交集，此需要将当前区间最小的两个数 xi 以及xi + 1加入到S中，同时更新 ls 为 xi + 1，rs 为 xi , 即贪心的取ls = xi, rs = xi + 1
若ls <= yi < rs，则有一个交集，此需要保留和区间[xi , yi]的交点，即使 ls ，另一个取能囊括区间更多点的点，即 xi ，将这两个点加入到S中，并更新 ls 和 rs ，即贪心的取 rs = ls，ls= xi
保证每次都是取左边界或者左边界和左边界+1

6.代码

//C++
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const vector<int> &a,const vector<int> &b)
{
    if(a[0]==b[0])//若左端一样，按照右边大到小排序
    {
        return a[1]>b[1];
    }
    return a[0]<b[0];
}
class Solution
{
public:
    int intersectionSizeTwo(vector<vector<int> > &ins)
    {
        //1.排序--左边升序，若左边相同，右边降序
        sort(ins.begin(), ins.end(),cmp);
        //2.从后往前遍历
        //取ins[n-1][0]和ins[n-1][0]+1作为开始的两个集合元素
        int res = 2, ls = ins.back()[0], rs = ls + 1;
        for(int i = ins.size() - 2; i >= 0; i--){
            if(ins[i][1] >= rs){  // 有两个及以上的交点
                continue;
            }else if(ins[i][1] < ls){  // 没有交点
                ls = ins[i][0];
                rs = ins[i][0] + 1;
                res += 2;
            }else{  // 一个交点
                rs = ls;
                ls = ins[i][0];
                res++;
            }
        }
        return res;
    }
};
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    Solution solve;
    int m;
    cin>>m;
    int data;
    vector<vector<int> >ins;
    for(int i=0;i<m;i++)
    {
        vector<int> row;
        for(int j=0;j<2;j++)
        {
            cin>>data;
            row.push_back(data);
        }
        ins.push_back(row);
    }
    int res=solve.intersectionSizeTwo(ins);
    cout<<res<<endl;
    return 0;
}