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:
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
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.
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.
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:
Here's a graphical schedule for this output:
Time 1 2 3 4 5 6 7 8 9 10Other outputs using the same number of stalls are possible.
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..
代码:
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; struct node { int x,y,ord,put; friend bool operator < (const node a,const node b) { if(a.y==b.y) return a.x>b.x; return a.y>b.y; } }; int cmp(struct node a,struct node b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int main() { int n; while(scanf("%d",&n)!=EOF) { int i,ans[50010]= {0},d=1; struct node s[50010]; priority_queue <node> q; for(i=0; i<n; i++) { scanf("%d%d",&s[i].x,&s[i].y); s[i].ord=i; } sort(s,s+n,cmp); q.push(s[0]); ans[q.top().ord]=d; for(i=1; i<n; i++) { if( s[i].x>q.top().y) { ans[s[i].ord]=ans[q.top().ord]; q.pop(); } else { d++; ans[s[i].ord]=d; } q.push(s[i]); } printf("%d ",d); for(i=0; i<n; i++) printf("%d ",ans[i]); } return 0; }