算法1

(贪心+优先队列)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn= 50100;
struct node
{
    int l, r;
    int x;
    bool operator <(const node &a)const 
    {
        if(r==a.r)
            return l>a.l;
        return r>a.r;
    }
}a[maxn];
priority_queue<node> p;//目前结束时间最早的一组从小到大排序 

int n,m,i,j,as[maxn];
bool cmp(node a, node b)
{
    return a.l == b.l? a.r<b.r : a.l<b.l;
}
int main()
{
    scanf("%d",&n);
    for( i = 1; i <= n; i ++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].x = i;
    }
    sort(a+1,a+1+n,cmp);//由开始时间从小到大排序 
    int ans = 0;
    for( i = 1; i <= n; i ++)
    {
        if(!p.empty() && p.top().r < a[i].l)//如果有组不空，并且最早结束的组比当前要放入的开始时间要早
        {                                   //就是准备放入的牛没有受到影响  
            as[a[i].x] = as[p.top().x];     //更新当前最早结束的 组 给新加入的牛标记上 
            p.pop();                        //将当前最早结束的组扔出来，因为他已经不是最早结束的了 
        }
        else
        {
            ans ++;                         //如果没有一个组符合要求，则组数加一 
            as[a[i].x] = ans;               //将新的牛放入新的组，并且更新新的组 
        }
        p.push(a[i]);                       //将更新后的组放入优先队列 
    }
    printf("%d\n",ans);
    for( i = 1; i <= n; i ++)
    printf("%d\n",as[i]);                   //按顺序输出每头牛放入的组 
    return 0;
}

```