题意:
最少拿走哪几个区间可以保证覆盖区间三个内至少有一对不相交
贪心做法,根据左端点进行排序,右端点大的优先被拿走,影响最小的保留,三个排序判断位置,队列维护下
index数组存一下下标。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=50005;
inline int read()
{
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
struct node
{
int l,r,id;
}a[maxn];
int ind[maxn];
bool cmp1(node a,node b)
{
return a.l<b.l;
}
bool cmp2(node a,node b)
{
return a.r<b.r;
}
bool cmp3(node a,node b)
{
return a.r>b.r;
}
int main()
{
int T,n,m;T=read();
while(T--)
{
int cou=0;
n=read();
for(int i=1;i<=n;i++)
{
a[i].l=read();
a[i].r=read();
a[i].id=i;
}
sort(a+1,a+n+1,cmp1);
vector<node> q;
q.push_back(a[1]);
q.push_back(a[2]);
for(int i=3;i<=n;i++)
{
q.push_back(a[i]);
sort(q.begin(),q.end(),cmp1);
if(q[1].l<=q[0].r&&q[2].l<=q[0].r&&q[2].l<=q[1].r)
{
sort(q.begin(),q.end(),cmp2);
ind[cou++]=q[2].id;
}
else sort(q.begin(),q.end(),cmp3);
q.pop_back();
}
sort(ind,ind+cou);
printf("%d\n",cou);
for(int i=0;i<cou-1;i++)
printf("%d ",ind[i]);
if(cou) printf("%d\n",ind[cou-1]);
}
return 0;
}