做网站案例,百度小说排行榜前十,免费域名注册网站源码,湖南省内出行最新政策假设有n个区间#xff0c;分别是#xff1a;[l1,r1], [l2,r2], [l3,r3].....[ln,rn] 从这n个区间中选出某些区间#xff0c;要求这些区间满足两两不相交#xff0c;最多能选出多少个区间呢#xff1f; 基本思路#xff1a; 按照右端点从小到大排序#xff0c;再比较左端… 假设有n个区间分别是[l1,r1], [l2,r2], [l3,r3].....[ln,rn] 从这n个区间中选出某些区间要求这些区间满足两两不相交最多能选出多少个区间呢 基本思路 按照右端点从小到大排序再比较左端点与前面覆盖的区域。每次选择左端点与前面的已经覆盖的区间不重合而右端点又尽量小的区间这样可以让剩下的未覆盖的区间尽可能的大就可以放置更多的区间。 实现
#includebits/stdc.h
using namespace std;
const int maxn 1001;
struct range{int left;int right;
}a[maxn];bool comp(range a, range b){if(a.right ! b.right){return a.right b.right;}return a.left b.left;
}
int main(){int n;cout n;cin n;for(int i0;in;i){cout 输入第 i1 个数\n;cout x ;cin a[i].left;cout y ;cin a[i].right; }int count1;sort(a,an,comp);int start a[0].right;cout (a[0].left,a[0].right)endl;for(int i1;in;i){if(a[i].leftstart){count;start a[i].right;cout (a[i].left,a[i].right)endl;}}cout count endl;}
