ZOJ-3953 Intervals 【贪心】

题目链接

题意

给N个区间，删掉其中一些区间，使得不存在任何三个互相相交区间。求删掉区间的最少数量以及哪些区间。

分析

贪心思路：先将所有区间按左端点从小到大排序（右端点无所谓）。选择当前左端点最小的三个区间，如果互相相交，删除右端点最大的区间；若不互相相交，将其中右端点最大的两个区间再与下一个区间进行判断。
正确性分析：由于是从左到右扫描，当前三个相交，去掉右端点最大的能够最大的减少对后面区间的影响；如果不相交，因为区间左端点递增，之后的区间肯定不会再跟这三个里面右端点最小的相交了，因此不用再考虑这个区间。

AC代码

//ZOJ-3953 Intervals
//AC 2017-4-10 20:46:18
//Greedy
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+100;

int T,n;
int res;
int ans[maxn];

struct inter
{
    int l;
    int r;
    int ID;
}inters[maxn],tmp[4];

bool cmp1(const inter &a,const inter &b)
{
    if(a.l==b.l)
        return a.r>b.r;
    return a.l<b.l;
}

bool cmp2(const inter &a,const inter &b)
{
    if(a.r==b.r)
        return a.l<b.l;
    return a.r>b.r;
}

bool intersect(const inter &a,const inter &b)
{
    if(a.l==b.l||a.r==b.r) return 1;
    if(a.l<b.l)
        return a.r>=b.l;
    else
        return b.r>=a.l;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        res=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d %d",&inters[i].l,&inters[i].r);
            inters[i].ID=i+1;
        }
        sort(inters,inters+n,cmp1);
        tmp[0]=inters[0];tmp[1]=inters[1];
        for(int i=2;i<n;++i)
        {
            tmp[2]=inters[i];
            sort(tmp,tmp+3,cmp2);
            if(intersect(tmp[0],tmp[1])&&intersect(tmp[0],tmp[2])&&
               intersect(tmp[1],tmp[2]))
               {
                ans[res++]=tmp[0].ID;
                tmp[0]=tmp[2];
               }
        }
        printf("%d
",res);
        sort(ans,ans+res);
        for(int i=0;i<res;++i)
            printf("%d ",ans[i]);
        printf("
");
    }
    return 0;
}