Stall Reservations

Time Limit: 1000MS Memory Limit: 65536K

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.

思路：

本题用了贪心+优先队列（没学的话可以学学，在贪心里还是挺常见的），本题要用尽量少的摊位让更多的奶牛生产，所以尽量能够让一个结束后，另一个能够接上，所以先排序将开始时间早的排前面，然后开始用优先队列，把结束时间早的排在前面，（把最早开始时间的放在前面，最早结束时间放在前面，如果这都接不上，那么肯定要开个摊位了），如果能接上的话，就将最早结束时间刷新，也就是说，这个摊位的最早结束时间变成了接上的那个奶牛的结束时间，需要注意的是加入1 4 和4 7必须要两个摊位，因为在4这个时间点，是两个奶牛都要在摊位里面，题目不允许，本题的摊位会发生没有奶牛生产，所以无需考虑队列为空这种情况。

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct NODE {
	int start;
	int end;
	int stall;
	int id;
	friend bool operator < (NODE a, NODE b) {
		return a.end > b.end;
	}
};
NODE node[50010];
bool cmp(NODE a, NODE b) {
	return a.start < b.start;
}
bool cmp2(NODE a, NODE b) {
	return a.id < b.id;
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> node[i].start >> node[i].end;
		node[i].id = i;
	} 
	sort (node, node + n, cmp);
	priority_queue<NODE> q;
	int num = 1;
	node[0].stall = num;
	q.push(node[0]);
	for (int i = 1; i < n; i++) {
		if (node[i].start > q.top().end) {
			node[i].stall = q.top().stall;
			q.pop();
			q.push(node[i]);
		} else {
			node[i].stall = ++num; 
			q.push(node[i]);
		}
	}
	cout << num << endl;
	sort(node, node + n, cmp2);
	for (int i = 0; i < n; i++) {
		cout << node[i].stall << endl;
	} 
	return 0;
}