poj1716 Integer Intervals 贪心

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
int left,right;
}c[10005];
bool cmp(node x,node y)//按照右端点排序
{
if(x.right<y.right) return true;
if(x.right==y.right&&x.left<y.left) return true;
return false;
}
int main()
{
int n,sum,l,r;
while(scanf("%d",&n)!=EOF)
{
memset(&c,0,sizeof(&c));
for(int i=0;i<n;i++)
scanf("%d %d",&c[i].left,&c[i].right);
sort(c,c+n,cmp);
l=c[0].right-1,r=c[0].right;
sum=2;
for(int i=1;i<n;i++)//贪心策略 每次总是和集合的倒数第二个数比较就ok了。。第一次比较傻 总是和倒数第一个数-1比较。。。很明显错了
{
if(c[i].left<=l)//如果小于等于 不加
continue;
else if(c[i].left<=r)//如果大于倒数第二 小于倒数第一+1
l=r,r=c[i].right,sum++;
else//如果大于倒数第一
l=c[i].right-1,r=c[i].right,sum+=2;
}
printf("%d\n",sum);
}
return 0;
}