N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering

最少数量的海报数.

#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define ll long long

using namespace std;

ll sta[300000],x,y;

int main(){

    int n,tp=0;   scanf("%d%lld%lld",&n,&x,&y);

    sta[++tp]=y;

    int ans=n;

    for(int i=1;i<=n-1;++i){

        scanf("%lld%lld",&x,&y);

        while(y<sta[tp]&&tp>0) --tp;

        if(tp && sta[tp]==y) --ans;

        sta[++tp]=y;

    }

    printf("%d",ans);

    return 0;

}