思路：
关于区间的贪心。
先对区间排序。再从前到后扫描，用堆维护当前最小的区间右端点right和对应的stall编号id，如果当前处理的区间的左端点大于right，则可以把这个区间放在编号为id的stall后面；否则重新开一个stall。
实现：
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <algorithm> 5 #include <functional> 6 using namespace std; 7 8 typedef pair<int, int> P; 9 struct node 10 { 11 int index, left, right; 12 }; 13 node a[50005]; 14 int cow[50005]; 15 int n; 16 priority_queue<P, vector<P>, greater<P> > pq; 17 18 bool cmp(const node & a, const node & b) 19 { 20 if (a.left != b.left) 21 { 22 return a.left < b.left; 23 } 24 return a.right < b.right; 25 } 26 27 int main() 28 { 29 cin >> n; 30 for (int i = 1; i <= n; i++) 31 { 32 a[i].index = i; 33 scanf("%d %d", &a[i].left, &a[i].right); 34 } 35 sort(a + 1, a + n + 1, cmp); 36 int cnt = 0; 37 pq.push(P(a[1].right, ++cnt)); 38 cow[a[1].index] = cnt; 39 for (int i = 2; i <= n; i++) 40 { 41 if (a[i].left > pq.top().first) 42 { 43 P tmp = pq.top(); 44 pq.pop(); 45 cow[a[i].index] = tmp.second; 46 P tmp2(a[i].right, tmp.second); 47 pq.push(tmp2); 48 } 49 else 50 { 51 pq.push(P(a[i].right, ++cnt)); 52 cow[a[i].index] = cnt; 53 } 54 } 55 cout << cnt << endl; 56 for (int i = 1; i <= n; i++) 57 { 58 cout << cow[i] << endl; 59 } 60 return 0; 61 }