F - Intervals ZOJ - 3953

F - Intervals ZOJ - 3953

按区间左端点排序，然后如果三个区间两两相交去掉r最大的
对于区间问题，不是按左端点就是右端点排序，重要的是想好贪心方法

#include<bits/stdc++.h>
using namespace std;

const int maxn = 50000+10;

struct Node{
    int l,r,id;
    bool del;
};
bool operator <(const Node &a,const Node &b){
    return a.l < b.l ||(a.l == b.l &&a.r < b.r);
}
bool  cmp(const Node &a,const Node &b){
    return a.r > b.r;
}
Node node[maxn];
int n;

int intersect(Node &a,Node &b,Node &c){
    // (a,b) (b,c),(a,c)
    return b.l <= a.r && c.l <= a.r && c.l <= b.r; 
}

int main(void){

    int T;
    cin>>T;
    while(T--){
        scanf("%d",&n);
        for(int i = 1;i <= n; ++i){
            scanf("%d%d",&node[i].l,&node[i].r);
            node[i].id = i;
        }
        sort(node+1,node+1+n);
        // cout<<"DEBUG"<<endl;
        std::vector<int> v;
        Node tmp[4];
        tmp[1] = node[1];
        tmp[2]  = node[2];
        for(int i = 3;i <= n; ++i){
            tmp[3] = node[i];
            sort(tmp+1,tmp+4);
            if(intersect(tmp[1],tmp[2],tmp[3]))
            {
                // cout<<i<<" "<<endl;
                // v.push_back(tmp[3].id);
                sort(tmp+1,tmp+4,cmp);
                v.push_back(tmp[1].id);
                swap(tmp[1],tmp[3]);
                // sort(tmp+1,tmp+4,cmp);
            }
            else
                sort(tmp+1,tmp+4,cmp);
            // cout<<i<<" "<<endl;
        }
        // cout<<"DEBUG"<<endl;
        sort(v.begin(),v.end());
        printf("%d\n",(int)v.size());
        for(int i = 0;i <(int) v.size(); ++i){
            printf("%d%c",v[i]," \n"[i==(int)v.size()-1]);
        }
        if((int) v.size() == 0)
            puts("");

    }


    return 0;
}