POJ 3190 Stall Reservations 贪心算法

优先队列 模拟处理一下

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1e5+10;
struct Node{
	int l,r,pos;
	bool operator < (const Node& b)const
	{
		return r > b.r;
	}
}node[maxn];
int order[maxn];
priority_queue<Node>Q;
bool cmp(Node &a,Node &b)
{
	return a.l < b.l;
}
int main()
{
	int n,ans=1;
	while(~scanf("%d",&n))
	{
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d%d",&node[i].l,&node[i].r);
			node[i].pos = i;
		}
		sort(node+1,node+1+n,cmp);
		Q.push(node[1]);
		order[node[1].pos] = 1;
		for(int i = 2; i <= n; ++i)
		{
			if(Q.top().r < node[i].l)
			{
				order[node[i].pos] = order[Q.top().pos];
				Q.pop();
			}
			else 
			{
				order[node[i].pos] = ++ans;
			}
			Q.push(node[i]);
		}
		printf("%d\n",ans);
		for(int i = 1; i <= n; ++i)
		printf("%d\n",order[i]);
		while(!Q.empty()) Q.pop();
	}
}