Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 提供思路！ 和比较容易错的情况！自己写了个快排＋贪心的！附代码！！！！（仅供参考）

Posted by 2007210562 at 2009-08-11 21:06:44 on Problem 2376
```首先，是对输入数据快排，最好定义个结构体！ 先按Start从小到大排序，如果相等，再按二维的从大到小排序。

#include <iostream>
#include <algorithm>
using namespace std;
struct Duan
{
int start;
int end;
};
struct Duan s[25005];
int comp (struct Duan a,struct Duan b)
{
return (a.start<b.start)||(a.start==b.start && a.end>b.end);
}

int main ()
{
int n,t,count,i,j,frist,second,tag,tag1;
scanf ("%d%d",&n,&t);
for (i=0;i<n;i++)
scanf ("%d%d",&s[i].start,&s[i].end);
sort(s,s+n,comp);
if (s[0].start==1)
{
if (s[0].end==t)
{
printf ("1\n");
}
else
{
count=1;
frist=second=s[0].end;
j=0;
tag=0;
while (1)
{
tag1=0;
for (i=1+j;i<n;i++)
{
if (s[i].start-1<=frist && second<s[i].end)
{
second=s[i].end;
j=i;
tag1=1;
}
}
if (tag1==0)
break;
count++;
if (second==t)
{
tag=1;
printf ("%d\n",count);
break;
}
frist=second;

}
if (tag==0)
printf ("-1\n");
}
}
else
printf ("-1\n");
return 0;
}
```

Followed by: