Stall Reservations

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4274		Accepted: 1530		Special Judge

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.

Line 1: A single integer, N 



Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.

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.

5

1 10

2 4

3 6

5 8

4 7

4

1

2

3

2

4

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.

<span style="font-size:18px;color:#3366ff;">#include <iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

struct Node{

     int s,e,id,num;

     bool operator<(const Node &a) const

     {

         return a.e<e;

     }

}node[50005];

int cmp(Node a,Node b)

{

     if(a.s!=a.s)

        return a.e<b.e;

     else return a.s<b.s;

}

int cmp2(Node a,Node b)

{

    return a.id<b.id;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

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

            {

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

                node[i].id=i;

            }

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

        priority_queue<Node>  q;

        node[1].num=1;

        q.push(node[1]);

        int cnt=1;

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

        {

             Node temp=q.top();

            if(node[i].s<=temp.e)

            {

                cnt++;

                node[i].num=cnt;

                q.push(node[i]);

            }

            else

            {

                node[i].num=temp.num;

                q.pop();

                q.push(node[i]);

            }

        }

        sort(node+1,node+n+1,cmp2);

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

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

            printf("%d\n",node[i].num);

     }

    return 0;

}</span>