1615:求区间

题目：
Description
在X轴上有n个闭区间，去掉尽可能少的区间使剩下的区间都不相交
Input
多组测试数据
第一行输入n（n<=1000）
接下来n行每行两个数a,b代表闭区间的两个端点。
（a,b<=1000000
Output
输出最小的删除的区间数
Sample Input
3
10 20
15 10
20 15
Sample Output
2

参考博客：https://blog.csdn.net/qq_41117236/article/details/81153752

思路：根据右边界做升序排序，每次作出的选择即为局部最优解，因为每一次的状态只依赖于前一次选取的状态，所以最后得到的结果为整体最优解。

AC代码：(侵删）

#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=300050;
struct qj{
    int x,y;
}q[maxn];
bool cmp(qj a,qj b){
    return a.y<b.y;
}
int main(){
   int t,temp;
    int m,n;
   while(~scanf("%d",&t)){
       for(int i=0;i<t;i++){
            scanf("%d%d",&q[i].x,&q[i].y);
            if(q[i].x>q[i].y) 
               temp=q[i].x, q[i].x=q[i].y, q[i].y=temp;
       }
   sort(q,q+t,cmp);
   int count=0,min=-1000005;
   for(int i=0;i<t;i++){
        q[i].x>min? min=q[i].y:count++;//重点 
        
    }
    printf("%d\n",count); 
    }
     return 0;
}