一本通 1.1 例 1【活动安排】

贪心即可，将活动按右端点排序，排序后能选则选。$O(n)$

证明：首先对于一个前面都为最优序列的前提下，如果对于一个活动$a$，使它发生是一种最优序列，然后再对于另一个活动$b$，它的结束时间比$a$早，并且开始时间也满足条件，那么根据贪心就可以选它，因为它既合法又是一种最优序列。

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, ans, last;
 5 struct Str {int l, r;}stu[1010];
 6 int cmp(Str a, Str b) {return a.r < b.r;}
 7 int main()
 8 {
 9     scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d %d", &stu[i].l, &stu[i].r);
10     sort(stu + 1, stu + n + 1, cmp);
11     for(int i = 1; i <= n; ++i)
12         if(stu[i].l >= last) 
13             last = stu[i].r, ++ans;
14     printf("%d", ans);
15     return 0;
16 }