算法分类：

区间分组的应用贪心

问题描述

有 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

输入样例：

输出样例：

实现步骤：

将所有牛按开始吃草的时间排序；
用小根堆维护当前所有畜栏的最后一头牛的吃草结束时间；
如果当前的牛可以安排在堆顶的畜栏中，则将其安排进去，否则就新建一个畜栏。

经典的区间分组问题。

实现代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> PII;
//cows.x.x为当前牛的吃草开始时间 cows.x.y为当前牛的吃草结束时间 cows.y为牛的编号
pair<PII,int> cows[N];
int n;
int id[N];
int main(){cin >> n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;cows[i].x.x = l;cows[i].x.y = r;cows[i].y = i;//存储编号}sort(cows,cows+n);priority_queue<PII,vector<PII>, greater<PII> > heap;for(int i=0;i<n;i++){if(heap.empty()||heap.top().x>=cows[i].x.x){id[cows[i].y] = heap.size();heap.push({cows[i].x.y,heap.size()});}else{auto stall = heap.top();heap.pop();stall.x = cows[i].x.y;heap.push(stall);id[cows[i].y] = stall.y;}}cout<<heap.size()<<endl;for(int i=0;i<n;i++) cout<<id[i]+1<<endl;return 0;
}