poj3190 stall revertation

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

Sample Output

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 = 50000;
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() + 1;//给新的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 = 0;i < N;i++) {
            scanf("%d%d", &cow[i].begin, &cow[i].end);
            cow[i].symbol = i;
        }
        sort(cow,cow+N);//开始时间小的牛排前面
        put_cow(0, true);
        for (int i = 1;i < N;i++) {
            put_cow(i, cow[i].begin <= que.top().end);//当前牛的开始值是否小于end值最小的stall的end值
        }
        cout << que.size()<<endl;
        for (int i = 0;i < N;i++)
            cout << result[i] << endl;

    }
    return 0;
}