南阳891--找点（区间覆盖）

找点

时间限制：2000 ms | 内存限制：65535 KB

难度：2

描述: 上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？

输入

多组测试数据。
每组数据先输入一个N，表示有N个闭区间（N≤100)。
接下来N行，每行输入两个数a，b(0≤a≤b≤100），表示区间的两个端点。

输出

输出一个整数，表示最少需要找几个点。

样例输入

样例输出

1
3
1

来源

原创

上传者

TC_李远航

//AC:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std ;
 4 struct node
 5 {
 6     int left ;
 7     int right ;    
 8 } ;
 9 node num[110] ;
10 
11 bool cmp(node left, node right)
12 {
13     return left.right < right.right ;
14 }
15 
16 int main()
17 {
18     int n, i, j ;
19     while(~scanf("%d", &n))
20     {
21         for(i=0; i<n; i++)
22         scanf("%d %d",&num[i].left, &num[i].right) ;
23         sort(num, num+n, cmp) ;
24         int total = 1 ;
25         for(j=0, i=0; i<n; i++)   //选点就选在区间右端点 ；通过更新j ；找到需要点数；
26         {
27             if(num[i].left > num[j].right)
28             {
29                 j = i ;
30                 total++ ;
31             }
32         }
33         printf("%d
", total) ;
34     }
35     return 0 ;
36 }