POJ 3190 -- Stall Reservations

http://poj.org/problem?id=3190
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.

还是该死的奶牛，这一回它们很淘气，每一只奶牛要求在时间区间[A,B]内独享一个牛栏。问最少需要多少个牛栏。
贪心策略是优先满足A最小的奶牛，维持一个牛栏B最小堆，将新来的奶牛塞进B最小的牛栏里。

通过这题学会了优先队列。优先队列用结构体的话需要在结构体里重载' < ' ，默认是最大值在队首。要想每次取出的是最小值，就在重载' < '时定义为大于。具体看代码

先以左端点为关键字进行排序。优先队列中存的是已经定位的线段，找出右端点最小的，看是否小于当前线段的左端点。若小于则弹出该线段，当前线段加入优先队列；若大于等于，则另开新行，当前线段加入优先队列。

Code from http://www.hankcs.com/program/cpp/poj-3190-stall-reservations.html

struct Section

{

    unsigned int index;

    unsigned int begin;

    unsigned int end;

    bool operator < (const Section& b) const 

    {  

        return begin < b.begin;

    } 

};

struct Stall

{

    unsigned int id;

    unsigned int end;

    bool operator < (const Stall& b) const 

    {  

        return end > b.end;

    }

    Stall(){}

    Stall(unsigned int id, unsigned int end):id(id), end(end){}

};

 

#define MAX_COWS 50000

Section cow[MAX_COWS];

unsigned int result[MAX_COWS]; // 每头牛从属于哪个牛栏

priority_queue<Stall> que; // 最小堆，储存所有牛栏区间的结束点（也就是最右端）

 

inline void put_cow(const int& i, const bool& new_stall)

{

    Stall s;

    if (new_stall)

    {

        s.id = que.size() + 1;

    }

    else

    {

        s.id = que.top().id; que.pop();

    }

    s.end = cow[i].end;

    result[cow[i].index] = s.id;

    que.push(s);

}

 

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int N;

    cin >> N;

 

    for (int i = 0; i < N; ++i)

    {

        cow[i].index = i;

        cin >> cow[i].begin;

        cin >> cow[i].end;

    }

 

    sort(cow, cow + N);

    put_cow(0, true);

 

    for (int i = 1; i < N; ++i)

    {

        put_cow (i, cow[i].begin <= que.top().end);

    }

 

    cout << que.size() << endl;

    for (int i = 0; i < N; ++i)

    {

        cout << result[i] << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Read full article from 3190 -- Stall Reservations