P1803 凌乱的yyy/线段覆盖

题目简述：

有n个区间，输入每个区间的开头和结尾，求出最多且没有重叠的区间数

知识点考察：

贪心算法

思路：

不重复区间这种题型要先按照每个区间的结尾从小到大排序

这样的排序有两种情况出现:

1. 第一个区间的头小于第二个区间的头

2. 第一个区间的头大于第二个区间的头

这个两种情况中的任意一种都是要选择第一个区间的，接下来就考虑要不要选择下面的区间的问题：如果第一个区间的尾大于第二个区间的头那么第二个区间就不选，用第一个区间的尾循环跟全部区间的头对比一次，将头比第一个区间尾大的区间全都筛除，然后再用第二个没有被筛掉的区间跟剩下的区间去比较。。。

中间用计数变量记住可以选上的区间的数量，最后输出

易错点：

第一次尝试时我是把区间头尾差从小到大排序，并且用数组模拟区间来记录是否重复，如果数组的计数>1就让ans++,这个经过多次判断之后就会出错，而且用了冒泡排序（采购赶紧去学排序！！）

代码：

#include <iostream>

#include <algorithm>/*sort排序*/

using namespace std;

const long long MAX=10000000;

struct information{

    long long a,b;

}zu[MAX];

int vis[MAX],ans;

bool com(information q,information p)/*sort排序的函数，用来排序区间的尾部*/

{

    return q.b<p.b;

}

int main()

{

    int n;

    cin>>n;

    for(int i=0;i<n;i++)cin>>zu[i].a>>zu[i].b;/*输入*/

    sort(zu,zu+n,com);/*排序*/

    for(int i=0;i<n;i++){

        if(!vis[i]){//判断是不是已经被筛除或者已经被选中

            ans++;

            vis[i]=1;//被选中标记为1

            for(int j=i+1;j<n;j++){

                if(zu[i].b>zu[j].a){//如果前一个的尾大于后面的头就筛除

                    vis[j]=1;//筛除标记为1

                }

            }

        }

    }

    cout<<ans;

}