题意

给出数轴上的$n$个区间，每个区间都是连续的$\text{int}$区间。 现在要在数轴上任意取一堆元素，构成一个元素集合$V$。 要求每个区间和元素集合$V$的交集至少有两个不同的元素。 求集合$V$最小的元素个数。

解题思路

贪心算法

先对所有区间按末端点排序 取第$i$个区间的最后两个元素$Selem$和$Eelem$ 若第$i + 1$个区间包含了这两个元素，则跳到下一个区间所取的元素个数$+0$ 若第$i + 1$个区间只包含了这两个元素中的一个（由于有序，所以必定是包含$Eelem$），则取第$i + 1$个区间的最后一个元素，所取的元素个数$+1$。为了方便下一区间的比较，更新$Selem$和$Eelem$的值，使他们为当前$V$集合中最后的两个元素。 若第$i + 1$个区间没有包含这两个元素，则第$i + 1$个区间的最后两个元素，所取的元素个数$+2$。为了方便下一区间的比较，更新$Selem$和$Eelem$的值，使他们为当前$V$集合中最后的两个元素。 $Selem$初始化为第一个区间的最后倒数第$2$个元素 $Eelem$初始化为第一个区间的最后的元素 所取的元素个数初始化为$2$ (就是$Selem$和$Eelem$)

标程

#include<iostream>
#include<algorithm>
using namespace std;

typedef class
{
public:
    int s,e;
}interval;

int cmp(const void* a,const void* b)
{
    interval* x=(interval*)a;
    interval* y=(interval*)b;
    return (x->e) - (y->e);
}

int main(void)
{
    int n;
    while(cin>>n)
    {
        interval* inter=new interval[n];

        for(int i=0;i<n;i++)
            cin>>inter[i].s>>inter[i].e;

        qsort(inter,n,sizeof(interval),cmp);

        int Selem=inter[0].e-1 , Eelem=inter[0].e;
        int sum=2;
        for(int k=1;k<n;k++)
            if(inter[k].s<=Selem)
                continue;
            else if(inter[k].s<=Eelem)
            {
                Selem=Eelem;
                Eelem=inter[k].e;
                sum++;
            }
            else
            {
                Selem=inter[k].e-1;
                Eelem=inter[k].e;
                sum+=2;
            }
        cout<<sum<<endl;

        delete[] inter;
    }
    return 0;
}