CSES – Room Allocation

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 2e5+5;
int n,ans[maxn];
vector<pii> v;
set<pii> st;
//
signed main(){
    fastio;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b; cin>>a>>b;
        v.push_back({a,b});
    }
    vector<int> ord(n); iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[](int i, int j){
        pii a = v[i], b = v[j];
        if(a.s == b.s) return a.f < b.f;
        else return a.s < b.s;
    });
    st.insert({0,1});
    int cnt = 1;
    for(int i:ord){
        int L = v[i].f, R = v[i].s;
        auto it = st.lower_bound({L,0});
        if(it == st.begin()){
            ans[i] = ++cnt;
            st.insert({R,cnt});
        }
        else{
            it--;
            auto [end_time, idx] = *it;
            ans[i] = idx;
            st.erase(it);
            st.insert({R,idx});
        }
    }
    cout<<cnt<<"\n";
    for(int i=0;i<n;i++) cout<<ans[i]<<" ";
    cout<<"\n";
    return 0;
}