题目链接：P1803

Describe:

现在各大 oj 上有 nnn 个比赛，每个比赛的开始、结束的时间点是知道的。 yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。 所以，他想知道他最多能参加几个比赛。 由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 222 个及以上的比赛。

Input:

第一行是一个整数 nnn ，接下来 nnn 行每行是 222 个整数 ai,bia_{i},b_{i}ai​,bi​ ( ai<bia_{i}<b_{i}ai​<bi​ )，表示比赛开始、结束的时间。

Output:

一个整数最多参加的比赛数目。

Sample Input:

3 0 2 2 4 1 3

Sample Output:

2

解题思路：

排序时要按每个比赛结束时间排增序，这样保证，选择那个比赛，结束时间都是一样的，对后面不产生影响，不然贪心策略可能不成立。

AC代码：

 

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 struct node
 5 {
 6     int st,ed;
 7     bool operator < (const node &tmp) const
 8     {
 9         if(ed == tmp.ed) return st < tmp.st;
10         else return ed < tmp.ed;
11     }
12 } a[1000010]; // 结构体数组记录开始结束时间
13 int main()
14 {
15     int n,x,y,s,cnt;
16     cnt = 0; // 记录参加比赛数
17     s = 0; // 记录时间点，初始化为零
18     cin >> n;
19     for(int i = 0; i < n ;i++)
20         cin >> a[i].st >> a[i].ed;
21     sort(a,a+n); // 排序
22     for(int i = 0; i < n; i++)
23     {
24         if(a[i].st >= s) // 如果当前开始时间点合适，就选择该比赛
25         {
26             s = a[i].ed;
27             cnt++;
28         }
29     }
30     cout << cnt;
31     return 0;
32 }