Stall Reservations - poj2385 - 贪心（详解）

Stall Reservations

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 10578	Accepted: 3738	Special Judge

Description

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows. 

Help FJ by determining:

• The minimum number of stalls required in the barn so that each cow can have her private milking period
• An assignment of cows to these stalls over time

Many answers are correct for each test dataset; a program will grade your answer.

Input

Line 1: A single integer, N 

Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.

Output

Line 1: The minimum number of stalls the barn must have. 

Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

5
1 10
2 4
3 6
5 8
4 7      

Sample Output

4
1
2
3
2
4      

Hint

Explanation of the sample: 

Here's a graphical schedule for this output: 

Time     1  2  3  4  5  6  7  8  9 10

Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>

Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..

Stall 3 .. .. c3>>>>>>>>> .. .. .. ..

Stall 4 .. .. .. c5>>>>>>>>> .. .. ..      

Other outputs using the same number of stalls are possible.

Source

USACO 2006 February Silver

题意：

牛在指定时间内产奶，该产奶时，棚子里只能一头牛，问，最少需要几个棚子 

思路：

• 为什么不按结束时间排序

被上学期算法里的活动安排问题深深洗脑，排的时候按照结束时间从小到大排了，结果就是WAWAWAWAWA……

现在知道为什么啦，活动安排问题是在一段指定的时间内，选出最大的活动相容数，这里的指定时间段是确定的一段，而在这题里这个不适用了，比如说：

5

1 3

2 4

2 5

4 6

5 7

这个用活动安排问题选出的活动是（1,3）（4,6），这是要4个棚子

然后，在这题里，给（1,3）（4,6）用一个棚子，（2,4）（5,7）用一个，（2,5）自己用一个，只需3个棚子

现在知道为什么不能只是仅仅地按照结束时间排序了吧，这样算出的是在Tmin~Tmax这段时间里可以同时进行的数目，和此题不一样啦

• 本题思路：

因为每个牛我们肯定都要它产奶的（一个牛都不能放弃），所以先按照开始时间从小到大排序，若开始时间同，按结束时间从小到大排序，然后用优先队列，按照结束时间从小到大排序，若下一个奶牛的开始时间大于当前奶牛的结束时间，则用一个棚子，让其棚子号和当前的棚子号相等，当前的出队，并把它入队，否则的话，ans++，棚子号等于ans，当前奶牛入队。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue> 
#include<vector>

using namespace std;

struct A{
	int l,r,seq;
}tim[50005],now;

int res[50005];

struct cmp1{
	bool operator ()(const A&a,const A&b) const{
		return a.r>=b.r;
	}
};

bool cmp(A a,A b){
	if(a.l==b.l){
		return a.r<b.r;
	}
	return a.l<b.l;
}
int n;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d",&tim[i].l,&tim[i].r);
		tim[i].seq=i;
	}
	sort(tim,tim+n,cmp);
	
	priority_queue<A,vector<A>,cmp1> qq;
	qq.push(tim[0]);
	int ans=1;
	
	res[tim[0].seq]=ans;
	
	for(int i=1;i<n;i++){
		now=qq.top();
		if(tim[i].l>now.r){
			res[tim[i].seq]=res[now.seq];
			qq.push(tim[i]);
			qq.pop();
		}
		else{
			ans++;
			res[tim[i].seq]=ans;
			qq.push(tim[i]);
		}
	}
	printf("%d\n",ans);
	
	for(int i=0;i<n;i++){
		printf("%d\n",res[i]);
	}	
}
/*
5
1 10
2 4
3 6
5 8
4 7
6
8 8
4 8
6 10
1 3
2 4
4 7
5
1 3
2 3
2 4
4 6
5 7
*/