区间贪心 不相交的区间最大个数

解题思路:

              贪心区间

             1.对区间左端点进行从大到小排序，左端点相同则按右端点从小到大排序；

             2.记录排列好的第一个被选中区间的左端点，如果下一个区间的右端点小于他，就选择；

注意事项:

要选中第一个元素，然后再比较

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct intver{
    int x,y;                //开区间左右端点
}I[1005];
int cmp(intver a,intver b)
{
    if(a.x!=b.x)       
    return a.x>b.x;    //先按左端点从大到小排列
    else
    return a.y<a.y;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&I[i].x,&I[i].y);
    }
    sort(I,I+n,cmp);
    int ans=1,lastx=I[0].x;        //ans记录不相交的区间个数，lastx记录上一个被选中区间的左端点，ans=1表示选了按照我的排列规则选了第一个
    for(int i=1;i<n;i++)
    {
        if(I[i].y<=lastx)//如果该区间右端点在lastx的左边，表示不相交，要选
        {
            lastx=I[i].x;   //以I[i]作为新的选中区间
            ans++;        //记录选择中的区间
        }
    }
    cout<<ans;
}