CodeForces 1101C Division and Union

題目大意

https://codeforces.com/problemset/problem/1101/C

多段區間，分成兩組，若不能保證從兩組中任取一個區間都不會相交，則輸出-1；能保證則輸出每段區間所在的組号（1、2）

題解

貪心+思維

按區間左端點從小到大排序；

第一段區間一定屬于第一組；

每周遊一段區間，判斷其左端點與第一組中全部區間的最大右端點的大小關系，若周遊到的區間的左端點大，則表示此段區間與任意一段屬于第一組的區間都不相交，此區間放在第二組，也可以推斷出其後面的均可以放在第二組保證不會與第一組的相交；若周遊到的區間的左端點小于第一組中全部區間的最大右端點，則說明此段區間不能放在第二組，放入第一組同時更新第一組的全部區間的最大右端點；

是以隻要找到第一個滿足“周遊到的區間的左端點大于第一組中全部區間的最大右端點”的區間即可，其之前的均為第一組，之後（含其）的均為第二組。

代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct node{
	int l, r, idx, group;
}a[N];

bool cmp(node u, node v) {
	return u.l == v.l?u.r < v.r:u.l < v.l;	
}
bool cmp1(node u, node v) {
	return u.idx < v.idx;
}
int main()
{
	int T, n;
	cin>>T;
	while(T--) {
		cin>>n;
		for(int i = 1;i <= n;i ++) cin>>a[i].l>>a[i].r, a[i].idx = i;
		sort(a+1, a+n+1, cmp);
		int k = 0;
		int rr = a[1].r;
		a[1].group = 1;
		for(int j = 2;j <= n;j ++) {
			if(rr >= a[j].l) rr = max(rr, a[j].r), a[j].group = 1;
			else {
				k = j;
				break;
			}
		}
//		for(int i = 1;i <= n;i ++) cout<<a[i].l << ' ' << a[i].r <<' '<<a[i].group<<endl;
		if(!k) cout<<"-1"<<endl;
		else {
			for(int i = k;i <= n;i ++) a[i].group = 2;
			sort(a+1, a+n+1, cmp1);
			for(int i = 1;i <= n;i ++) cout<<a[i].group<<' ';
			puts("");
		}
	} 

	return 0;
}