题目描述

有N头牛在畜栏中吃草。

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

给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。

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

输入格式
第1行：输入一个整数N。

第2..N+1行：第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B，数之间用空格隔开。

输出格式
第1行：输入一个整数，代表所需最小畜栏数。

第2..N+1行：第i+1行输入第i头牛被安排到的畜栏编号。

数据范围
$1≤N≤50000$
$1≤A,B≤1000000$

样例

输入样例：
5
1 10
2 4
3 6
5 8
4 7
输出样例：
4
1
2
3
2
4

贪心+小根堆

这道题目的重点在第二问,因此我们可以选择这样的做法,首先排序这群奶牛,然后我们可以以时间轴为基础,每一头奶牛为枚举点即可,具体看代码实现.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=50100;
struct node
{
    int l;
    int r;
    int x;
    bool operator <(const node &a)const 
    {
        if(r==a.r)
            return l>a.l;
        return r>a.r;
    }
} a[N];
priority_queue<node> p;
int n,m,i,j,as[N];
int cmp(node a,node b)
{
    if (a.l==b.l)
        return a.r<b.r;
    return a.l<b.l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>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]);
    }    
    cout<<ans<<endl;
    for (i=1;i<=n;i++)
        cout<<as[i]<<endl;
    return 0;
}