创作于2019年5月10日 @ 下午2:17

#include<queue> 
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 50010
using namespace std;

int n,ans;
int order[M];
struct Node{
	int st,en,pos;
	friend bool operator < (Node x,Node y){
		if(x.en==y.en)
			return x.st<y.st;
		else 
			return x.en>y.en;
	}
}a[M];
priority_queue <Node> Q;

bool cmp(Node x,Node y){
	if(x.st==y.st)
		return x.en<y.en;
	else
		return x.st<y.st;
}

int main(){
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i].st,&a[i].en);
			a[i].pos=i;
		}
		sort(a+1,a+n+1,cmp);
		ans=1;
		Q.push(a[1]);
		order[a[1].pos]=1;
		for(int i=2;i<=n;i++){
			if(!Q.empty()&&Q.top().en<a[i].st){
				order[a[i].pos]=order[Q.top().pos];
				Q.pop();
			}
			else{
				ans++;
				order[a[i].pos]=ans;
			}
			Q.push(a[i]);
		}
		printf("%d\n",ans);
		for(int i=1;i<=n;i++)
			printf("%d\n",order[i]);
		while(!Q.empty()) Q.pop();
	}
	return 0;
}

 

0 0 votes
文章评分
0 评论
Inline Feedbacks
View all comments