POJ：3190-Stall Reservations

传送门：http://poj.org/problem?id=3190

Stall Reservations

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 9173 Accepted: 3208 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.

---

解题心得：

1. 题意就是每个牛在一段时间内要产奶，每个奶牛在产奶的时候必须给它安排一间屋子，问最少需要多少间屋子，以及给每个奶牛安排产奶的屋子是第几间。
2. 也就是一个思维题 ，先把奶牛用起始时间拍个序，用一个优先队列1来放所有的屋子编号，再用一个优先队列2来记录每个奶牛产奶结束的时间，遇到一个奶牛开始产奶，就看优先队列2中在当前时间是否有奶牛已经结束产奶了，如果已经结束产奶，就将安排给那个产奶的奶牛屋子还回队列1当中，然后从队列1中找一个编号最小的屋子给当前的奶牛。优先队列1中出现的房间号数字最大的就是最少需要安排的房间数。

---

#include <stdio.h>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn = 5e4+100;

struct COW {

    int s,e,num;

    bool operator <(const COW & a) const {

        return a.e < e;

    }

}cow[maxn];

int n;

bool cmp(COW a,COW b) {

    if(a.s  == b.s)

        return a.e < b.e;

    return a.s < b.s;

}

void init() {

    for(int i=1;i<=n;i++) {

        scanf("%d%d",&cow[i].s,&cow[i].e);

        cow[i].num = i;

    }

    sort(cow+1,cow+n+1,cmp);

}

int ans[maxn];

void get_ans() {

    int Max_num = -1;

    priority_queue <int,vector<int>,greater <int> > qu;

    priority_queue <COW> qu2;

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

        qu.push(i);

    for(int i=1;i<=n;i++) {

        COW now = cow[i];

        while(!qu2.empty() && qu2.top().e < now.s) {

            qu.push(ans[qu2.top().num]);

            qu2.pop();

        }

        ans[now.num] = qu.top();

        if(qu.top() > Max_num)

            Max_num = qu.top();

        qu.pop();

        qu2.push(cow[i]);

    }

    printf("%d\n",Max_num);

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

        printf("%d\n",ans[i]);

}

int main() {

    scanf("%d",&n);

    init();

    get_ans();

    return 0;

}