题目描述

Description

约翰有N(1≤N≤100000)头奶牛，它们都可以控制自己的产奶量．一头产奶不多的奶牛会被其它奶牛嘲笑, 约翰制订一张产奶时间表，第i头奶牛在Ai_Bi时间段里产奶(0≤Ai < Bi ≤ 10^9)．这头奶牛必须在Ai的时候进入奶棚在Bi的时候离开．奶棚的门很小，同一时刻只能有一头奶牛通过． 如果第i头奶牛产奶的时间段包含第j头奶牛产奶的时间段，即A < Aj < Bj < Bi.那么，我们称这两个时间段是“巢段”． “巢段”是一件很糟糕的事，因为第j头奶牛在奶棚的时间里第i头奶牛一直都在．这样第i头奶牛就能估计第j头奶牛的产奶量．由于产奶量被别的奶牛知道了的奶牛会发疯，所以约翰不希望“巢段”的发生．
帮助约翰确定最大的k(1 ≤ K ≤ N)，在1到K的奶牛中不存在“巢段”．

Input

第1行：奶牛的数量N．
第2到N+1行：每行有两个用空格隔开的数字，表示这头奶牛的产奶时间段．

Output

一个整数K

Sample Input

5
7 20
1 4
3 12
6 10
0 3

Sample Output

3

题目分析

STL大法好 使用set维护pair 没见过这么写的

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct your
{
    int x,y;
}a[100010]; 
typedef pair<int,int> par;
set<par> s;
set<par>::iterator it;
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);   
    for(int i=1;i<=n;i++)
    {
        par tmp=make_pair(-a[i].x,-a[i].y);
        it=s.upper_bound(tmp);
        if(it!=s.end()&&-it->second >a[i].y)
        {
            printf("%d",i-1);
            return 0;
        }
        s.insert(tmp);
    }
    printf("%d",n);
    return 0;
}