选择尽可能多的不相交区间

选择尽可能多的不相交区间,第1张

题目:有n个区间,[ai, bi), 统计不相交区间最多有多少个?

贪心策略:将这n个区间按bi由小到大排序,然后从前向后遍历,每当遇到不相交的区间就加入目标集合,遍历完成后就找到了最多的不相交区间。

正确性证明:参见http://blog.csdn.net/dgq8211/article/details/7534488

以下是HDUOJ2037的源代码:

#include <iostream>
#include <iomanip>
#include <cmath>
#define PI 3.1415927
using namespace std;

struct Activity {
	int s, t;
};

void bubbleSort(Activity *ac, int size) {
	for(int i=0; i<size-1; i++) {
		for(int j=0; j<size-1-i; j++) {
			if(ac[j].t>ac[j+1].t) {
				int tempS = ac[j].s;
				ac[j].s = ac[j+1].s;
				ac[j+1].s = tempS;
				
				int tempT = ac[j].t;
				ac[j].t = ac[j+1].t;
				ac[j+1].t = tempT;
			}
		}
	}
}

int main()
{
	int n;
	while(cin>>n) {
		if(n==0) break;
		Activity *ac = new Activity[n];
		for(int i=0; i<n; i++) {
			cin >> ac[i].s >> ac[i].t;
		}
		bubbleSort(ac, n);
		int count = 1;//第一个肯定要加进来
		
		int t = ac[0].t;//维护不相交区间集合最大的t
		for(int i=1; i<n; i++) {
			if(ac[i].s>=t) {
				count++;
				t = ac[i].t;
			}
		}
		cout << count << endl;
		delete[]ac;
	}
	return 0;
}


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/2082800.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-07-22
下一篇 2022-07-22

发表评论

登录后才能评论

评论列表(0条)

保存