POJ 3190 stall reservations (greedy interval problem + priority queue maintenance)

Question meaning: a group of individual cows only produce milk at a fixed time. Each cow needs to use a milking machine. Ask how many milking machines are needed at least to meet the needs of all cows, and output the number of the milking machine according to the order given by the cows.

First, the cows are sorted from small to large according to the start time of milk production. If the start time is the same, the cows are sorted from small to large according to the end time. Then a priority queue of priority end time is used to maintain the current milk producing cow. If the start time of the next cow is less than or equal to the end time of the current cow, a milk producing machine needs to be reused and incorporated into the queue. If it is greater than the end time of the current cow, a milking machine can be used together and the current milk producing cow can be updated.

The code is as follows:

  1. #include<cstdio>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. #include<queue>  
  5. using namespace std;  
  6. int per[50010];  
  7. struct node  
  8. {  
  9.     int start,end,pos;  
  10. }cow[50010],now;  
  11.   
  12. bool operator < (const node &a,const node &b)//The earlier the end of lactation, the better  
  13. {  
  14.     if(a.end==b.end)  
  15.         return a.start>b.start;  
  16.     return a.end>b.end;  
  17. }  
  18.   
  19. int cmp(node a,node b)  
  20. {  
  21.     if(a.start==b.start)  
  22.         return a.end<b.end;  
  23.     return a.start<b.start;  
  24. }  
  25.   
  26.   
  27.   
  28. int main()  
  29. {  
  30.     int n,i,k,cnt;  
  31.     while(scanf("%d",&n)!=EOF)  
  32.     {  
  33.         for(i=0;i<n;++i)  
  34.         {  
  35.             scanf("%d%d",&cow[i].start,&cow[i].end);  
  36.             cow[i].pos=i;//Record the number when the data is given  
  37.         }  
  38.         sort(cow,cow+n,cmp);      
  39.         memset(per,0,sizeof(per));  
  40.         priority_queue<node>q;  
  41.         q.push(cow[0]);  
  42.         per[cow[0].pos]=1;  
  43.         k=1;  
  44.         for(i=1;i<n;++i)  
  45.         {  
  46.             now=q.top();  
  47.             if(cow[i].start>now.end)//Same milking machine  
  48.             {  
  49.                 per[cow[i].pos]=per[now.pos];  
  50.                 q.pop();  
  51.             }  
  52.             else//Add a milking machine  
  53.                 per[cow[i].pos]=++k;  
  54.             q.push(cow[i]);  
  55.         }  
  56.         printf("%d\n",k);  
  57.         for(i=0;i<n;++i)  
  58.             printf("%d\n",per[i]);  
  59.     }  
  60.     return 0;  
  61. }   


Tags: less

Posted on Mon, 30 Mar 2020 12:10:07 -0700 by saleemshehzad