赛后复盘--对于E题只能通过33.33%的思考，线段的排序优先级问题

链接：https://ac.nowcoder.com/acm/contest/103948/E
来源：牛客网

题目描述

在数轴上，一共有 n 条线段，小红已经将所有线段都染成了红色。小紫准备至少选择一条线段，将它们都染成紫色，并且使得不存在两个红色的线段相交，也不存在两个紫色的线段相交。
小紫能成功吗？如果可以，请你帮小紫输出一个染色方案，如果不可以，请输出-1。

思路

对于每一条线段，存储其左端点l，右端点r，以及其编号index
然后开一个vector<int>A，B，分别用于存储需要染成紫色/红色的线段集合，vector内存储线段的编号
然后对于线段排序（cmp函数）
之后遍历线段，将互不相交的线段编号存入集合A中，如果在此期间遇到了与集合A中线段存在相交的线段，判断其是否与集合B中的所有线段都互不相交，如果是，则放入B中，如果不是，则输出-1（因为这一条线段不管是被染红/紫，都会与至少一条与其同色的线段相交）
最后的答案就是A.size()，输出的线段编号就是A中存入的线段编号
（所以集合B可以省略，下面的AC代码是集合B省略的情况）

如何判断一条线段是否与集合A/B中的线段存在相交的情况
一种高效的方法是设两个变量edA,edB，分别表示A集合/B集合内含有线段的最大右端点
对于一条线段是否属于集合A，如果其左端点（下面统称L）>edA（不能等于是因为端点相交也算相交），那么表示这一条线段肯定不与集合A中的任何线段重合，所以可以直接加入集合A，并且将edA的值设为其右端点（下面统称R）的值;
如果L<=edA，那么再看L是否>edB，如果L>edB，那么表示这一条线段肯定不与集合B中的任何线段重合，所以可以直接加入集合B，并且将edB的值设为其R的值;
如果L<=edB，那么表示这一条线段不与集合A和集合B中的任何线段重合，直接输出-1即可

接下来是比较函数的写法，下面是两种比较函数

错误的比较函数（只能通过33.33%） 

int cmp(node a,node b) {
	if(a.r!=b.r)return a.r<b.r;
    return a.l<b.l;
}

正确的比较函数（AC） 

int cmp(node a,node b) {
    if(a.l!=b.l)return a.l<b.l;
    return a.r < b.r;
}
由于采用了上面判断线段一条线段是否与集合A/B中的线段存在相交的方法，所以这里的排序一定是要用第二种的（第一种样例能过，但是分析一下就会发现有问题）
如下面的例子所示：
4
1 3
2 5
6 7
4 8
可以发现，对于第一种先排R的比较，输出为-1（显然不正确），对于第二种先排L的比较，输出为2(换行)1 4，显然是正确的
画个图看看为什么会这样

可以清晰的发现，主要的问题其实就是L端点的问题，因为本着A集合“能放就放”的原则，所以如果按r排，对于本来应该放入集合B的线段6-7，集合A会直接将其放入，从而导致集合A,B都无法放入线段4-8（有点像想贪心，结果贪错了？）
但是如果按L排，则不会出现这一情况，原因其实就是其确保了集合用贪心取线段的正确性，确保集合内的线段在互不相交的同时，彼此之间靠的最近
而如果按R排，其集合内的线段虽然同样互不相交，但是彼此之间无法保证靠的最近（由于L的不确定性（注：if(a.r!=b.r) return a.l<b.l）并不能使得L有序！），从而导致部分本来可以存下的线段无法被存下，或是导致存入的集合不是最优的那一个，造成错误
所以应该先按L排
（为什么我赛时想错了呢qwq）

下面是AC代码 

#include<bits/stdc++.h>
#define endl "\n"
#define int long long int
using namespace std;
const int N=4e5+200;
struct node {
	int l,r;
	int index;
}d[N];
vector<int>A;
int cmp(node a,node b) {
	if(a.l!=b.l)return a.l<b.l;
    return a.r < b.r;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>d[i].l>>d[i].r;
		d[i].index=i;
	}
	sort(d+1,d+1+n,cmp);
	int edA=-1, edB=-1;
	for (int i=1;i<=n;i++) {
		if (d[i].l > edA) {
			A.push_back(d[i].index);
			edA=d[i].r;
		} else if (d[i].l > edB) {
			edB=d[i].r;
		} else {
			cout<<"-1"<<endl;
			return 0;
		}
	}
	int si=A.size();
	cout<<si<<endl;
	for (int i=0; i<si; i++) {
		if (i>0) cout<<" ";
		cout<<A[i];
	}
	cout<<endl;
	return 0;
}
注：这里取A集合是一定对的，但是取B集合则不一定对。这是因为如果输入数据的线段全部互不相交的话，线段会全部存在A集合里，导致B.size()==0，但是输出要求为正整数（>0），此时输出B.size()的话显然不合法