我一开始想用线段树，但是发现还要记录每头cow所在的棚......

无奈之下选择正解：贪心。

用priority_queue来维护所有牛棚中结束时间最早的那个牛棚，即可得出答案。

注意代码实现的细节。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int N = 50010; 6 struct Cow { 7     int a, b, num; 8     bool operator < (const Cow& x) const { 9         return this->a < x.a;10     }11     bool operator > (const Cow& x) const {12         return this->a > x.a;13     }14 }c[N];15 priority_queue< Cow, vector
         
          , greater
          
            >Q;16 int ans[N];17 int main() {18     int n, top = 0;19     scanf("%d", &n);20     for(int i = 1; i <= n; i++) {21         scanf("%d%d", &c[i].a, &c[i].b);22         c[i].num = i;23     }24     sort(c + 1, c + n + 1);25     Cow x;26     x.a = c[1].b;27     x.b = ++top;28     ans[c[1].num] = top;29     Q.push(x);30     for(int i = 2; i <= n; i++) {31         //printf("i:%d c[i].b:%d Q.top().a:%d\n", c[i].num, c[i].b, Q.top().a);32         if(Q.top().a < c[i].a) {33             x = Q.top();34             Q.pop();35             x.a = c[i].b;36             ans[c[i].num] = x.b;37             Q.push(x);38         }39         else {40             x.a = c[i].b;41             x.b = ++top;42             ans[c[i].num] = top;43             Q.push(x);44         }45     }46     printf("%d\n", top);47     for(int i = 1; i <= n; i++) {48         printf("%d\n", ans[i]);49     }50     return 0;51 }