原题传送门

类似题传送门（代码相同）

题目描述

给定N个闭区间[ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数N，表示区间数。

接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
1≤N≤105,
−109≤ai≤bi≤109

思路

读到这题，先考虑暴力。结果发现这范围大得一塌糊涂，很快就被卡了。可知行不通，必须优化。

我们可以想到，当一个数上有点时，包含这个数的区间都会被满足。因此，我们在推理时，应尽可能“一箭多雕”。

接着，我们的目标就转化为“如何尽可能完美地放点”。一个区间，若放较前，则无法顾及后面；若放较后，则无法顾及前面。既然如此，我们就应该有规律地放（从前往后或从后往前，此处讲从前往后）。故先要储存，排序。

要排序，就得有关键字。关键字分为二：1.起点、2.终点。若以起点为关键字，我们就不知道点该尽量往哪放。既然从前往后，理应尽量往后放，因为其他区间都在自己后面。可万一有一个区间起点在自己之后，终点在自己之前，那么它就会被巧妙地避开，最后WA。

所以，我们要以终点为关键字。这样，我们只要将点放在终点的数上就能将尽可能多的区间满足。

步骤

1、输入;
2、储存;
3、排序;
4、处理;
5、输出。

参考代码(C++)

#include<bits/stdc++.h>
using namespace std;

struct body{  //  储存区间;
    int z,y,me;
    //  me  区间的序号;
}s[100000+10];
int zw[100000+10];
//  zw[]  排好了的区间序号;
int p[100000+10];
//  p[]  判断区间是否满足;
int y[100000+10];
//  y[]  排好了的区间终点;
bool empy(body a,body b){  //  终点排序;
    return a.y<b.y;
}
bool empx(body a,body b){  //  起点排序;
    return a.z<b.z;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&s[i].z,&s[i].y);
        s[i].me=i;
    }  //  输入&&储存;
    sort(s+1,s+1+n,empy);  //  终点排序;
    for(int i=1;i<=n;i++){
        y[i]=s[i].y;
        zw[i]=s[i].me;
    }  //  储存起来;
    sort(s+1,s+1+n,empx);
    int z=1,ans=0;
    for(int i=1;i<=n;i++){
        if(p[zw[i]]) continue;  //  若已满足，则next;
        while(z<=n&&y[i]>=s[z].z){  //  范围内&&可满足;
            p[s[z].me]=1;
            ++z;
        }
        ++ans;
        if(z>n) break;
    }
    printf("%d",ans);
    return 0;
}

若有不足，敬请指出。