POJ.3190 Stall Reservations

1.Problem:
http://poj.org/problem?id=3190

2.Idea:
Pick items from earlier starting order, and use priority_queue as data structure to simulate stall stations.

3.Source

 struct Interval {  
      int start, end, num;  
      bool operator < (const Interval &a)const {  
           return end>a.end;  
      }  
 } Cows[50004];  
 bool comp(Interval a, Interval b)  
 {  
      if (a.start == b.start) {  
           return a.end < b.end;  
      }  
      else return a.start < b.start;  
 }  
 int n;  
 int ans[50004];  
 int cur = 1;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d%d", &Cows[i].start, &Cows[i].end);  
           Cows[i].num = i;  
      }  
      sort(Cows, Cows + n, comp);  
      priority_queue<Interval> q;  
      q.push(Cows[0]);  
      ans[Cows[0].num] = cur;  
      for (int i = 1; i < n; i++) {  
           if (q.top().end < Cows[i].start) {  
                int tmp = ans[q.top().num]; q.pop();  
                ans[Cows[i].num] = tmp;  
                q.push(Cows[i]);  
           }  
           else {  
                cur++;  
                ans[Cows[i].num] = cur;  
                q.push(Cows[i]);  
           }  
      }  
      cout << cur << endl;  
      for (int i = 0; i < n; i++) {  
           printf("%d\n", ans[i]);  
      }  
      return 0;  
 }