AcWing 111. 畜栏预定()

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 n头牛和每头牛开始吃草的时间 A 以及结束吃草的时间

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

#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;
 }
————————

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 n头牛和每头牛开始吃草的时间 A 以及结束吃草的时间

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

#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;
 }