企业官网建设流程全解析

设置交集大小至少为2

作者: Turbo

时间限制: 1s

章节: 贪心

问题描述

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

输出

5

思路

1. 排序
   将所有区间按照右端点升序排序，如果右端点相同，则按左端点降序排序。这样能优先处理“更紧迫”的区间。

2. 维护当前集合 S 中最大的两个数
   用两个变量last1和last2（last1 < last2）表示已经选入集合的最大的两个元素。
   因为更小的元素对后续区间（右端点越来越大）的覆盖能力更弱，所以我们只关心最大的两个点。

3. 遍历每个区间[l, r]
   先计算当前last1和last2中有几个落在当前区间内：

   • 若last1 >= l，则两个点都在区间内，cnt = 2；

   • 若last1 < l且last2 >= l，则只有last2在区间内，cnt = 1；

   • 若last2 < l，则没有一个点在区间内，cnt = 0。

   根据cnt决定需要补充几个点：

   • cnt == 2：已经满足，跳过；

   • cnt == 1：还需要 1 个点，贪心选择r（当前区间右端点），因为它最靠右，最有利于覆盖后面的区间；

   • cnt == 0：还需要 2 个点，贪心选择r-1和r（注意区间长度至少为 2，所以r-1 >= l），同样也是尽量靠右。

   每次添加点后，用新点更新last1和last2（始终保持它们为当前集合中最大的两个数），同时答案计数加 1 或 2。

4. 最后输出答案，即最少需要选取的元素个数。

5. # include<bits/stdc++.h> using namespace std; int n; typedef struct{ int a; int b; }P; int last1 = -1 ; int last2 = -1 ; vector<P> v; int cmp(P p1,P p2){ if(p1.b!=p2.b) return p1.b<p2.b; return p1.a>=p2.a; } int fun(int num,P p){ if(num>=p.a&&num<=p.b) return 0; else return 1; } int main(){ cin>>n; v.resize(n); for(int i=0;i<n;i++){ P p; cin>>p.a>>p.b; v[i] = p; } sort(v.begin(),v.end(),cmp); int ret = 0; for(int i=0;i<n;i++){ int temp = 0; temp+=fun(last1,v[i]); temp+=fun(last2,v[i]); if(temp==0) continue; if(temp==1){ last2 = last1; last1 = v[i].b; ret+=1; } else{ last2 = v[i].b-1; last1 = v[i].b; ret+=2; } } cout<<ret; }