# AcWing 111. 畜栏预定()-其他

## AcWing 111. 畜栏预定()

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+3;
int n;
struct T{
int id,l,r;
bool operator<(const T &rh)const{
if(r==rh.r) return l>rh.l;
return r>rh.r;
}
}a[N];
int ans[N];
priority_queue<T> q;
int cmp(T &A,T &B){
if(A.l==B.r) return A.r<B.r;
return A.l<B.l;
}
signed main(){
cin>>n;
int i,cnt=0;
for(i=1;i<=n;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
sort(a+1,a+1+n,cmp);

for(i=1;i<=n;i++){
if(q.empty()==0&&a[i].l>q.top().r){
ans[a[i].id]=ans[q.top().id];
q.pop();
}
else cnt++,ans[a[i].id]=cnt;
q.push(a[i]);
}
cout<<cnt<<endl;
for(i=1;i<=n;i++) cout<<ans[i]<<endl;
}

————————

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+3;
int n;
struct T{
int id,l,r;
bool operator<(const T &rh)const{
if(r==rh.r) return l>rh.l;
return r>rh.r;
}
}a[N];
int ans[N];
priority_queue<T> q;
int cmp(T &A,T &B){
if(A.l==B.r) return A.r<B.r;
return A.l<B.l;
}
signed main(){
cin>>n;
int i,cnt=0;
for(i=1;i<=n;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
sort(a+1,a+1+n,cmp);

for(i=1;i<=n;i++){
if(q.empty()==0&&a[i].l>q.top().r){
ans[a[i].id]=ans[q.top().id];
q.pop();
}
else cnt++,ans[a[i].id]=cnt;
q.push(a[i]);
}
cout<<cnt<<endl;
for(i=1;i<=n;i++) cout<<ans[i]<<endl;
}