开放原子开发者工作坊

题目：有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;
}