官方题解

【算法分析】

当只有两个活动（两个时间段）的时候，选择参加哪个都是可以的，当有第三个活动的时候，这时候就会发现优先选择前两个结束较早的那个活动，才能完整的看第三个活动，所以尽早看完一个活动就有机会参加其它活动（也就是按结束时间从早到晚排序）。

【参考代码】

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
	int s, e;//开始时间，结束时间
}a[1010]; 

bool cmp(node a, node b) {
	return a.e < b.e;
}

int main() {
	int n, num = 1;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i].s >> a[i].e;
	sort(a, a + n, cmp);
	int last = a[0].e;
	for (int i = 1; i < n; i++) {
		if (a[i].s >= last) { //下一个活动的开始时间大于等于下一个活动的结束时间
			num++;
			last = a[i].e;
		}
	}
	cout << num;
	return 0;
}

【时间复杂度】

$O(nlog_2n)$

【预计得分】

$100pts$