30 设置交集大小至少为2

作者: Turbo时间限制: 1S章节: 贪心

晚于: 2020-07-22 12:00:00后提交分数乘系数50%

截止日期: 2020-07-29 12:00:00

问题描述 :

一个整数区间 [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}.

可使用以下main函数：

int main()

{

int m,n,data;

vector<vector<int> > intervals;

cin>>m;

for(int j=0; j<m; j++)

{

vector<int> aRow;

for(int i=0; i<2; i++)

{

cin>>data;

aRow.push_back(data);

}

intervals.push_back(aRow);

}

int res=Solution().intersectionSizeTwo(intervals);

cout<<res;

return 0;

}

输入说明 :

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

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

输出说明 :

输出一个整数

输入范例 :

4 1 2 2 3 2 4 4 5

输出范例 :

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    static bool vcmp(vector<int>&a,vector<int>&b)
    {
        return a[0]==b[0]?a[1]>b[1]:a[0]<b[0];
    }
    int intersectionSizeTwo(vector<vector<int>>& intervals)
    {
        sort(intervals.begin(),intervals.end(),vcmp);//按区间起点升序 区间终点降序
        int len=intervals.size();
        
        
        vector<int> num(len,2);//每个区间需找交点个数
        int i=len,ans=0;
        while(--i>=0)
        {
            for(int val=intervals[i][0];val<intervals[i][0]+num[i];val++)//若第i个区间还需要找到num[i]个交点 从第i个区间依次取前num[i]个值 记为val
            {
                for(int j=i-1;j>=0;j--)
                {
                    if(num[j]&&val<=intervals[j][1]) //如果第j个num[j]不为0 且第j个区间的终点大于等于val
                        num[j]--;
                } 
            }
            ans+=num[i];//结果加上第i个区间 加到集合中值的个数
        }
        return ans;

    }
};
int main()
{
    int m,n,data;
    vector<vector<int> > intervals;
    cin>>m;
    for(int j=0; j<m; j++)
    {
        vector<int> aRow;
        for(int i=0; i<2; i++)
        {
            cin>>data;
            aRow.push_back(data);
        }
        intervals.push_back(aRow);
    }

    int res=Solution().intersectionSizeTwo(intervals);
    cout<<res;

    return 0;

}
/*
     //首先itervals按照起点升序 终点降序排序
    //为每个区间设置一个todos变量 里面存储的是本区间还需要找到 存在于交集的元素的个数 
    //因为交集长度至少是2 所以初始时都为2
    //从后往前遍历 如果todo[i]>0 则取出这个区间的前todo[i]个 这里使用了贪心
    //贪心的思想是每次在一个区间 取的个数为这个区间所需要取的个数的最小值 取的值为这个区间的最小值
    //每次取的值为val，同时更新res res++
    //再从此位置 更新下标i之前的todos
    //若第j个位置的右端点小于等于val 则todos[j]--
    static bool cmp(vector<int>& a,vector<int>& b)
    {
        return a[0]==b[0]?a[1]>b[1]:a[0]<b[0];
    }
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        //按区间起点升序 区间终点降序
        sort(intervals.begin(),intervals.end(),cmp);
        int size=intervals.size();
        cout<<size<<endl;
        //每个区间还需要找到的交点的个数
        vector<int> todos(size,2);
        int i=size,res=0;
        while(--i>=0)
        {
            //若第i个区间还需要找到todos[i]个交点 从第i个区间依次取前todos[i]个值 记为val
            for(int val=intervals[i][0];val<intervals[i][0]+todos[i];val++)
                //实际上所有val构成的值就是集合S
                //更新i之前的todos
                for(int j=i-1;j>=0;j--)
                    //如果第j个todos[j]不为0 且第j个区间的终点大于等于val
                    if(todos[j]&&val<=intervals[j][1])
                        todos[j]--;
            cout<<todos[i]<<endl;
            res+=todos[i];//结果加上第i个区间 加到集合中值的个数
            //todos[i]=0;//这句为了完整性更新 实际上不更新也对结果无影响
        }
        return res;

*/
//https://www.cnblogs.com/happyamyhope/p/10429434.html