今年暑假不AC（贪心思路）

这道题是一道贪心算法的经典问题（活动选择问题）
先说用到的贪心结论：最先结束的活动一定是最优解的一部分

证明过程如下：
假设a是所有活动中最先结束的活动，b是最优解中最先结束的活动
如果a=b 则结论成立
如果a!=b 则b的结束时间一定晚于a的结束时间，则此时用a替换掉最优解中的b，
a一定不与最优解中的其他活动时间重叠，因此替换掉后也是最优解

 
#include<iostream>
#include<algorithm>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct program {
	int s;
	int e;
};
 
int cmp(program a, program b) {
	return a.e < b.e;
}
 
int main() {
	int n; program time[110];
	while (~scanf("%d", &n) && n) {
		memset(time, 0, sizeof(time));
		int i;
		for (i = 0; i < n; i++) {
			scanf("%d%d", &time[i].s, &time[i].e);
		}
		sort(time, time + n, cmp);
		int temp = time[0].e, count = 1;
		for (i = 1; i < n; i++) {
			if (time[i].s >= temp) {
				count++;
				temp = time[i].e;
			}
		}
		printf("%d\n", count);
	}
	return 0;
}