| ||||||||||
| 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 | |||||||||
sort + 贪心,直接附代码#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct inter{
int s, g;
inter(int s = 0, int g = 0): s(s), g(g) {}
bool operator < (const inter& b) const {
if(this->s != b.s)
return this->s < b.s;
else
return this->g < b.g;
}
};
const int maxn = 25000+5;
const int INF = 1e8;
int N, T;
inter itv[maxn];
int tanxin()
{
int ans = 0, g;
int left = upper_bound(itv, itv+N, inter(1, INF)) - itv;
int right;
if(left == 0)
return -1;
else
{
left--;
g = itv[left].g;
ans++;
}
while(g < T)
{
right = upper_bound(itv+left, itv+N, inter(g+1, INF)) - itv;
g = 0;
int maxpos = -1;
for(int i = left+1; i<right; i++)
{
if(itv[i].g > g)
{
maxpos = i;
g = itv[i].g;
}
}
if(maxpos == -1)
return -1;
else
{
left = maxpos;
ans++;
}
}
return ans;
}
int main()
{
scanf("%d %d", &N, &T);
for(int i = 0; i<N; i++)
scanf("%d %d", &itv[i].s, &itv[i].g);
sort(itv, itv+N);
int ans = tanxin();
printf("%d\n", ans);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator