C++区间覆盖(贪心算法)

• 算法结构

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

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

基本思路：

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

实现：

#include

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;
	for(int i=0;i<n;i++){
		cout << "输入第" << i+1 << "个数\n";
		cout <> a[i].left;
		cout <> a[i].right;
	}


	int count=1;
	sort(a,a+n,comp);
	int start = a[0].right;
	cout <<"("<=start){
			count++;
			start = a[i].right;
			cout <<"("<

                                                        
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/db90f380a4.html
赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐