题目描述

有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≤500001≤N≤50000
1≤A,B≤1000000

样例

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

如果两头牛吃草的时间段有重合，需要增加牛栏，对牛吃草的最小时间排序记录并更新每个牛栏的牛吃草最晚时间，每次与队列中最小的最晚时间比较，如果

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=5e4+10;
typedef pair<int,int>Pll;
pair<Pll,int>a[N];
int id[N];//记录每头牛所在牛围栏
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].first.first>>a[i].first.second;
        a[i].second=i;//记录牛的编号
    }
    sort(a,a+n);//排序
    priority_queue<Pll,vector<Pll>,greater<Pll>>p;//小根堆，堆顶是最小值，存储每个牛围栏
    for(int i=0;i<n;i++)
    if(p.empty()||p.top().first>=a[i].first.first)//堆为空或者堆顶与牛吃草有重合部分
    {
        Pll t={a[i].first.second,p.size()};//第一个位置存储该牛围栏的牛吃草最晚时间
        id[a[i].second]=t.second+1;//加1，是因为原本有一头牛
        p.push(t);
    }
    else
    {
        auto t=p.top();
        p.pop();
        t.first=a[i].first.second;//更新最晚时间
        id[a[i].second]=t.second+1;
        p.push(t);
    }
    cout<<p.size()<<endl;
    for(int i=0;i<n;i++) cout<<id[i]<<endl;
    return 0;
}