网站后台管理进不去了,管理咨询公司怎么开展业务,做书app下载网站,做网站什么一级导航二级导航假设有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;}
