时间限制：2000 ms | 内存限制：65535 KB 难度：2 描述
上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？
输入多组测试数据。
每组数据先输入一个N，表示有N个闭区间（N≤100)。
接下来N行，每行输入两个数a，b(0≤a≤b≤100），表示区间的两个端点。 输出输出一个整数，表示最少需要找几个点。 样例输入
4 1 5 2 4 1 4 2 3 3 1 2 3 4 5 6 1 2 2
样例输出
1 3 1
此题为贪心区间取点问题，先将区间右端b按从小到大排序
当b相等时将a按从大到小排序，这样则小区间在大区间上边；
将第一个区间的右端b赋值给j，然后依次与以下区间的左端a比较
若大于以下区间的左端a，则证明有公共区间，当j大于后边的区间
左边a时，证明与以上区间无重合部分则 m++；左后输出m
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct record
{
int beg;
int end;
}num[101];
bool cmp(record a,record b) //排序 将区间右边按从小到大排序
{
if(a.end!=b.end)
return a.end<b.end; //区间左边 在右边的基础上从大到小排序
else
return a.beg>b.beg;
}
int main()
{
int n,m,j,i,s,t;
while(scanf("%d",&n)!=EOF)
{
j=0;
for(i=0;i<n;i++)
scanf("%d %d",&num[i].beg,&num[i].end);
sort(num,num+n,cmp);
j=num[0].end;m=1;
for(i=1;i<n;i++) //当下一个区间的左边大于开始赋值的数 j
{ //则将此区间 的右边赋值给j
if(num[i].beg>j)
{
j=num[i].end;
m++;
}
}
printf("%d\n",m);
}
return 0;
}
原文：http://www.cnblogs.com/tonghao/p/4374731.html