题目描述

有N头牛在畜栏中吃草。

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

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

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

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

输入格式

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

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

输出格式

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

第2..N+1行：第i+1行输入第i头牛被安排到的畜栏编号，编号从1开始，只要方案合法即可。

数据范围

1≤N≤50000
1≤A,B≤1000000

样例

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

输出样例：
4
1
2
3
2
4

首先,想到一个直觉正确的贪心方法是:

将n头牛按照开始时间从小到大排列,然后用一个小根堆维护当前结束时间最早的畜栏.考虑到第i头牛时,如果能将其安排到当前结束时间最短的畜栏,则将其塞入;否则,则为它新建一个畜栏.

下面我们来证明这个贪心的正确性
首先,对于每头牛,我们只有两种选择:塞入之前的畜栏或为它新建畜栏
在能选择前一种的情况下,我们不需要选择后一种.因为在排完序的情况下,每头牛开始吃草的时间严格不降.对于后面的牛来说,一个将第i头牛塞入的原有畜栏和新建畜栏是没有区别的,因为后面的每头牛失去了挤在第i头牛前面的机会(受开始时间限制).因为这样,我们只需要用结束时间对每个畜栏加以区分.所以其实只要能塞,第i头牛塞哪里都行,这也就证明了进阶指南上$O(n^2)$算法的正确性.只是我们如果一个个找未免过于繁琐,不如来个痛快的,用小根堆维护最早的结束时间,若这个畜栏都塞不进去那肯定塞不进去别的了,只好新建畜栏.时间复杂度降至$o(nlongn)$
证毕.

一些需要注意的细节在代码注释中给出

代码参考:

#include <cstdio>
#include <map>
#include <algorithm>
#include <queue>
const int maxn=50000+10;
using namespace std;
pair<pair<int, int>, int> a[maxn];//开始时间,结束时间,编号
//pair默认以first来进行比较,
priority_queue<pair<int, int> > s;//维护当前最早的结束时间,注意优先队列默认大根堆
//first存畜栏最后一头牛的编号,second存当前畜栏结束时间
int f[maxn];//每头牛的归宿

int Num(int x) {return a[x].second;}
int Start(int x) {return a[x].first.first;}
int End(int x) {return a[x].first.second;}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].first.first,&a[i].first.second);
        a[i].second=i;
    }
    sort(a+1, a+1+n);
    f[Num(1)]=1;
    s.push(make_pair(-End(1), Num(1)));//为第一头牛新建畜栏
    int cnt=1;//畜栏个数
    for (int i=2;i<=n;i++)
    {
        if (Start(i)>-s.top().first)
        {
            f[Num(i)]=f[s.top().second];
            s.pop();//更换结束时间
        }
        else
            f[Num(i)]=++cnt;
        s.push(make_pair(-End(i), Num(i)));
    }
    printf("%d\n",cnt);
    for (int i=1;i<=n;i++)
        printf("%d\n",f[i]);
    return 0;
}