h0215.闭区间问题

警察设置n个对历史时间线的监控点，每个监控点可监控历史上的一个时间段，我们可以简单地看做是 x 轴上 n 个闭区间。但有些监控点监控的时间段是重叠的，这会干扰监控的准确性。请尝试去掉尽可能少的闭区间，使剩下的闭区间都不相交。

输入格式:

第一行为闭区间的个数n（1≤n≤40000），随后n行为闭区间的２个端点。

输出格式:

输出去掉尽可能少的闭区间的个数。

输入样例:

3
10 20
15 10
20 15

输出样例:

2

 //问题 C: 【贪心】闭区间问题_0k-ok的博客-CSDN博客

sort 函数排序之cmp浅析_sort cmp_星河欲转。的博客-CSDN博客

//本题借鉴了该博主，从思路上来说，就是将区间两边首先按从小到大排序，然后关键点在于最后for循环那个判断，在该循环中，j=0,i=1&&i

#include<bits/stdc++.h>
using namespace std;
struct xx{
int a,b;
}s[40005];
int cmp(xx x,xx y){
    if(x.b==y.b)return x.a<y.a;
    return x.b<y.b;
}
int main(){
    int n,c=0,j=0;
   cin>>n;
    for(int i=0;i<n;i++){
       cin>>s[i].a>>s[i].b;
        if(s[i].a>s[i].b)//将所有左区间大于右区间的数交换
            swap(s[i].a,s[i].b);
    }
    sort(s,s+n,cmp);
    c+=1;
    for(int i=1;i<n;i++){
        if(s[i].a>s[j].b){
            c++;
            j=i;
        }
    }
   cout<<n-c;
    return 0;
}