| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题没这么难啊,区间贪心#include<stdio.h>
#include<algorithm>
#define M 25005
using namespace std;
int N,T;
struct node
{
int x;
int y;
}A[M];
bool cmp(node a,node b)
{
if(a.x != b.x)
return a.x < b.x;
else
return a.y > b.y;
}
int main()
{
int i,j,str,end;
int ans,end2;
while(~scanf("%d%d",&N,&T))
{
for(i=0;i<N;i++)
scanf("%d%d",&A[i].x,&A[i].y);
sort(A,A+N,cmp);
if(A[0].x != 1)
{
printf("-1\n");
continue;
}
ans = 1;
end2 = 0;
end = A[0].y;
for(i=1;i<N;i++)
{
if(A[i].x > end+1)
{
end = end2;
ans++;
}
if(A[i].x <= end+1 && A[i].y >= end+1)
{
if(A[i].y > end2)
end2 = A[i].y;
if(A[i].y == T)
{
end = T;
ans++;
break;
}
}
}
if(end != T)
printf("-1");
else
printf("%d\n",ans);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator