一、内容
有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
二、思路
区间分组问题。我们判断一个区间是否能加入一个组，就与这个组的max_r（区间）进行比较,若大于它那么就可以添加到这个组。若不大于它那么就新开一个组我们用小根堆来维护已经开了的组的所有max_r,我们取最小的max_r，若这个组连最小的max_r都不大于，那么只能重开一个组。
三、代码
#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std
;
const int N
= 5e4 + 5;
struct Range
{
int l
, r
, id
;
friend bool operator <(Range a
, Range b
) {
if (a
.l
== b
.l
) return a
.r
< b
.r
;
return a
.l
< b
.l
;
}
}niu
[N
];
struct Group
{
int no
, num
;
friend bool operator <(Group a
, Group b
) {
if (a
.num
== b
.num
) return a
.no
< b
.no
;
return a
.num
> b
.num
;
}
Group(int no
, int num
):no(no
), num(num
) {}
};
int n
, l
, r
, ans
[N
];
priority_queue
<Group
> q
;
int main() {
scanf("%d", &n
);
for (int i
= 0; i
< n
; i
++) {
scanf("%d%d", &niu
[i
].l
, &niu
[i
].r
);
niu
[i
].id
= i
;
}
sort(niu
, niu
+ n
);
for (int i
= 0; i
< n
; i
++) {
if (q
.empty() || q
.top().num
>= niu
[i
].l
) {
ans
[niu
[i
].id
] = q
.size() + 1;
q
.push(Group(q
.size() + 1, niu
[i
].r
));
} else {
int temNo
= q
.top().no
;
ans
[niu
[i
].id
] = temNo
;
q
.pop();
q
.push(Group(temNo
, niu
[i
].r
));
}
}
printf("%d\n", q
.size());
for (int i
= 0; i
< n
; i
++) {
printf("%d\n", ans
[i
]);
}
return 0;
}
