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
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; }
标签:xi,rs,交集,ins,力扣,int,ls,设置,区间 From: https://www.cnblogs.com/ohye/p/17589452.html