题目描述
有n个点和m个区间，点和区间的端点全部是整数，对于点a和区间[b,c]，若a> =b且a< =c，称点a满足区间[b,c]。
求最小的点的子集，使得所有区间都被满足。

数据规模和约定
1< =n,m< =10000
0< =点和区间的坐标< =50000
输入
第一行两个整数n m
以下n行 每行一个整数，代表点的坐标
以下m行 每行两个整数，代表区间的范围
输出
输出一行，最少的满足所有区间的点数，如无解输出-1。
样例输入
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9
样例输出
2
提示
C语言在线学习平台微信号dotcpp
来源
算法提高

思路：
1.首先将每个区间按照右边界从小到大进行排序
2.然后把每个点从大到小进行排序，这样便可以使用lower_bound函数找倒第一个小于等于某个值的点
3.使用x记录上一个点的值，初始化为-1，这样方便处理
4.当一个区间的左边界大于x时候，需要从所有剩下的点中找到第一个小于等于右边界的点。如果没有找到，错误，如果找到的点不满足要求，也是错误。

#include<iostream>
#include<algorithm> 
#include<vector>
using namespace std;
const int N=10010,M=10010;
typedef struct {
    int L,R;
}region;
region re[M];
vector<int>point;
bool cmp(region a,region b)
{
    return a.R<b.R; 
} 
int main(void)
{
    int n,m,x,cnt=0,yes=true;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        point.push_back(x);
    }
    for(int i=1;i<=m;i++) cin>>re[i].L>>re[i].R;
    sort(re+1,re+m+1,cmp);
    sort(point.begin(),point.end(),greater<int>());
    x=-1;
    for(int i=1;i<=m;i++)
    {
        if(x<re[i].L)
        {
            vector<int>::iterator it=lower_bound(point.begin(),point.end(),re[i].R,greater<int>());
            if(it==point.end())
            {
                yes=false;
                break;
            }
            x=*it;
            point.erase(it);
            cnt++;
            if(x<re[i].L)
            {
                yes=false;
                break;  
            }   
        }   
    } 
    if(yes) cout<<cnt;
    else cout<<-1;
    return 0;
}