E - Intervals 贪心

时间:2021-09-29 06:21:06

Chiaki has n intervals and the i-th of them is [li, ri]. She wants to delete some intervals so that there does not exist three intervals a, b and c such that a intersects with b, b intersects with c and c intersects with a.

Chiaki is interested in the minimum number of intervals which need to be deleted.

Note that interval a intersects with interval b if there exists a real number x such that laxra and lbxrb.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n ≤ 50000) -- the number of intervals.

Each of the following n lines contains two integers li and ri (1 ≤ li < ri ≤ 109) denoting the i-th interval. Note that for every 1 ≤ i < jn, lilj or rirj.

It is guaranteed that the sum of all n does not exceed 500000.

<h4< dd="">Output

For each test case, output an integer m denoting the minimum number of deletions. Then in the next line, output m integers in increasing order denoting the index of the intervals to be deleted. If m equals to 0, you should output an empty line in the second line.

<h4< dd="">Sample Input

1
11
2 5
4 7
3 9
6 11
1 12
10 15
8 17
13 18
16 20
14 21
19 22

<h4< dd="">Sample Output

4
3 5 7 10
E - Intervals
题目大意:
就是给你n组数据,在这n组数据里,删除一部分,使得任意三个组数据不相交。
题目思路:
先对它开始的位置进行排序,小的在前,然后取三组数据,进行判断是否两两相交,如果是就先要对它进行排序。
这个排序比较重要,是以结束的数据为标准,数据越大排在越前面。
如果两两相交就删去之后排序在最前面的那组数据,否则就更新一个为最后那组数据。
其实比较想清楚就比较简单了,分成两组数据进行处理,第一组以l进行排序,第二组以r进行排序,如果要删除,就删除r最大的
那组数据,再更新一个数据。值得学习的是,这种处理方法,这样子可以很好的处理表示删除的数据。
 
不过这里要注意一下,对是不是两两相交判断的标准,就是先选两个例如x,y,先满足x与y相交,再加入z,z与x,z与y相交
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=50050;
struct node
{
int l,r,id;
}ex[maxn];
int ans[maxn]; bool cmp1(node a,node b)
{
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
bool cmp2(node a,node b)
{
if(a.r==b.r) return a.l<b.l;
return a.r>b.r;
}
int isinterval(node x,node y,node z)
{
int f1=0,f2=0;
if(x.r>=y.l) f1=1;//x&y
if(x.r>=z.l&&y.r>=z.l) f2=1;//z&x,z&y
if(f1&&f2) return 1;
return 0;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,pos=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&ex[i].l,&ex[i].r);
ex[i].id=i+1;
}
sort(ex,ex+n,cmp1);
node x[5];
x[0]=ex[0];
x[1]=ex[1];
for(int i=2;i<n;i++)
{
x[2]=ex[i];
// sort(x,x+3,cmp1);
int f=isinterval(x[0],x[1],x[2]);
sort(x,x+3,cmp2);
if(f)
{
ans[pos++]=x[0].id;
swap(x[0],x[2]);
}
}
sort(ans,ans+pos);
printf("%d\n",pos);
if(pos==0) printf("\n");
else
{
for(int i=0;i<pos-1;i++) printf("%d ",ans[i]);
printf("%d\n",ans[pos-1]);
}
}
return 0;
}