设置交集大小至少为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;vectorvectorint intervals;cinm;for(int j0; jm; j){vectorint aRow;for(int i0; i2; i){cindata;aRow.push_back(data);}intervals.push_back(aRow);}int resSolution().intersectionSizeTwo(intervals);coutres;return 0;}输入说明首先输入intervals 的区间个数m范围为[1, 3000]然后输入m行每行2个数字 [0, 10^8]范围内的整数表示区间的左、右边界。输出说明输出一个整数输入41 22 32 44 5输出5思路排序将所有区间按照右端点升序排序如果右端点相同则按左端点降序排序。这样能优先处理“更紧迫”的区间。维护当前集合 S 中最大的两个数用两个变量last1和last2last1 last2表示已经选入集合的最大的两个元素。因为更小的元素对后续区间右端点越来越大的覆盖能力更弱所以我们只关心最大的两个点。遍历每个区间[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。最后输出答案即最少需要选取的元素个数。# includebits/stdc.h using namespace std; int n; typedef struct{ int a; int b; }P; int last1 -1 ; int last2 -1 ; vectorP v; int cmp(P p1,P p2){ if(p1.b!p2.b) return p1.bp2.b; return p1.ap2.a; } int fun(int num,P p){ if(nump.anump.b) return 0; else return 1; } int main(){ cinn; v.resize(n); for(int i0;in;i){ P p; cinp.ap.b; v[i] p; } sort(v.begin(),v.end(),cmp); int ret 0; for(int i0;in;i){ int temp 0; tempfun(last1,v[i]); tempfun(last2,v[i]); if(temp0) continue; if(temp1){ last2 last1; last1 v[i].b; ret1; } else{ last2 v[i].b-1; last1 v[i].b; ret2; } } coutret; }