河南网站制作公司哪家好广州推广优化

假设有n个区间，分别是：[l1,r1], [l2,r2], [l3,r3].....[ln,rn]

从这n个区间中选出某些区间，要求这些区间满足两两不相交，最多能选出多少个区间呢？

基本思路：

        按照右端点从小到大排序，再比较左端点与前面覆盖的区域。每次选择左端点与前面的已经覆盖的区间不重合而右端点又尽量小的区间，这样可以让剩下的未覆盖的区间尽可能的大，就可以放置更多的区间。

实现：

#include<bits/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 i=0;i<n;i++){cout << "输入第" << i+1 << "个数\n";cout << "x = ";cin >> a[i].left;cout << "y = ";cin >> a[i].right;		}int count=1;sort(a,a+n,comp);int start = a[0].right;cout <<"("<<a[0].left<<","<<a[0].right<<")"<<endl;for(int i=1;i<n;i++){if(a[i].left>=start){count++;start = a[i].right;cout <<"("<<a[i].left<<","<<a[i].right<<")"<<endl;}}cout << count << endl;}