Stall Reservations
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 5469 | Accepted: 1973 | 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.
题意：有N头牛，每头牛都有不同的进食时间段，求至少多少个牛棚，使得每个牛棚每个时间段最多只有一头牛在吃东西。
思路：
若每个牛棚的总区间为[A,B],每头牛的进食阶段分别为[begin_i,end_i](i=1,2,3....N),则先对每头牛的开始时间begin_i从小到大排序,先将第一头牛压入第一个stall中，之后的牛循环压入stall中，每次尽量将begin_i最小的牛先压入stall中，当前stall若装不下（由于后面的stall的end值越来越大，更装不下），则需要增加新的一个stall，所有的stall都存储在最小堆中（priority_queue）,在堆中尽量让结束时间早的stall放在最上面。最后输出最小堆中stall的数量即可。
AC代码如下:
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N_MAX = ;
struct section{
unsigned int begin;
unsigned int end;
unsigned int symbol;
bool operator <(const section &b)const {
return begin < b.begin;
}
}; struct stall {
unsigned int begin;
unsigned int end;
unsigned int symbol;
bool operator <(const stall&b)const{//return回来的是常量，习惯性的加const
return end > b.end;
}
};
section cow[N_MAX];
unsigned int result[N_MAX];//记录每一头牛在哪个stall
priority_queue<stall>que;//最小优先队列，stall中end小的放在堆的上面 inline void put_cow(const int &i,const bool &new_stall) {
stall s;
if (new_stall) {//需要存放在新的stall的情况
s.symbol = que.size() + ;//给新的stall贴上标号
}
else {
s.symbol = que.top().symbol;
que.pop();
}
s.end = cow[i].end;//压入牛后更新stall中end的值
result[cow[i].symbol] = s.symbol;//记录每一头牛放在什么stall中
que.push(s);
} int main() {
int N;
while (cin >> N) {
for (int i = ;i < N;i++) {
scanf("%d%d", &cow[i].begin, &cow[i].end);
cow[i].symbol = i;
}
sort(cow,cow+N);//开始时间小的牛排前面
put_cow(, true);
for (int i = ;i < N;i++) {
put_cow(i, cow[i].begin <= que.top().end);//当前牛的开始值是否小于end值最小的stall的end值
}
cout << que.size()<<endl;
for (int i = ;i < N;i++)
cout << result[i] << endl; }
return ;
}