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
*/