《算法竞赛进阶指南》畜栏预定

畜栏预定

有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≤500001≤N≤50000,
1≤A,B≤10000001≤A,B≤1000000
输入样例：
5
1 10
2 4
3 6
5 8
4 7
输出样例：
4
1
2
3
2
4

本题利用的是贪心的思想，首先先说明做法，在说明它的正确性：先将牛吃草的时间段按起始时间降序排序，然后开一个存储pair< int , int >的小根堆（按第一个元素降序排序），第一个存储牛吃草的终止时间，第二个放应该属于哪个栅栏，然后分析第i个牛，将第i个牛的起始时间与堆顶的第一个元素（堆顶牛的终止时间）进行比较当第i个牛的起始时间大时，可以代替当前堆顶的牛放到当前的栅栏中，否则要开一个新法栅栏.

简单证明:首先假设现在有m个栅栏，第i个牛需要判断：

第i个牛的起始时间一定比前m个牛的起始时间大，所以只有当前牛的起始时间大于某一栅栏的终止时间时，两者才没有交集才能公用一个栅栏。

有人可能会问有没有这种情况出现

这是不可能的因为我们之前是将牛按起始时间降序排序的这样的第i头牛应该早就判断过了

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
#define pii pair<int ,int >
const int maxn=50010;
int id[maxn];//存储每个牛在那个栅栏里
pair<pii ,int > cows[maxn];//cows数组first 存储这头牛吃草的起点和终点 
//second 记录当前牛是第几头牛
int n;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>cows[i].first.first>>cows[i].first.second;
		cows[i].second=i;
	}
	sort(cows+1,cows+1+n);//对数组排序（依据第一个元素排序，也就是牛的吃草的起始时间）
	priority_queue<pii, vector<pii> , greater<pii > >heap;
	//建立小根堆动态存储每一个栅栏的情况
	//每一个元素 ,first 记录当前栅栏最后一个牛的终止时间， second 记录当前栅栏是第几个栅栏 
 	for(int i=1;i<=n;i++)
	{
		if(heap.empty()||heap.top().first>=cows[i].first.first)
		{
			pii stall ={cows[i].first.second,heap.size()+1};
			id[cows[i].second]=stall.second;
			heap.push(stall);
		}
		else
		{
			auto stall= heap.top();
			heap.pop();
			stall.first=cows[i].first.second;
			id[cows[i].second]=stall.second;
			heap.push(stall);
		}
	}
	cout<<heap.size()<<endl;
	for(int i=1;i<=n;i++)
	cout<<id[i]<<endl;
	return 0;
}