POJ-3190 Stall Reservations---优先队列+贪心

题目链接：

题目大意：

有N头奶牛，每头奶牛都会在[1,1000000]的时间区间内的子区间进行挤奶。挤奶的时候奶牛一定要单独放在一个牛棚中。一头奶牛的结束时间与另一头奶牛的开始时间重合的时候2头奶牛不能放在同一个牛棚中，例A牛时间[5,10]，B牛时间[10,12]，那么需要用2个牛棚放这2头牛。输入N头牛的所有的挤奶时间区间，要求输出最少要建几个牛棚，以及每头牛挤奶的时候在第几号牛棚。

思路：

将奶牛根据挤奶开始时间排序后，从第一只奶牛进行考虑。从牛棚的优先队列中返回结束时间最短的牛棚，看该奶牛是否能放在该牛棚中。如果能，就更新该牛棚的结束时间，更新为该奶牛的开始时间；如果不能，就新创建一个牛棚，并将奶牛放在这个牛棚中。重复以上，直到所有奶牛都被放完。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 typedef pair<int, int> Pair ;
 9 typedef long long ll;
10 const int INF = 0x3f3f3f3f;
11 const int maxn = 1e5 + 10;
12 int T, n, m, cases;
13 struct node
14 {
15     int x, y, id;
16     bool operator <(const node a)const
17     {
18         return y > a.y;
19     }
20 };
21 bool cmp(node a, node b)
22 {
23     return a.x < b.x || a.x == b.x && a.y < b.y;
24 }
25 node a[maxn];
26 int id[maxn];
27 int main()
28 {
29     cin >> n;
30     for(int i = 1; i <= n; i++)
31     {
32         scanf("%d%d", &a[i].x, &a[i].y);
33         a[i].id = i;
34     }
35     sort(a + 1, a + n + 1, cmp);
36     priority_queue<node>q;
37     int ans = 1;
38     id[a[1].id] = 1;
39     q.push(a[1]);
40     for(int i = 2; i <= n; i++)
41     {
42         node now = q.top();
43         if(a[i].x > now.y)
44         {
45             q.pop();
46             id[a[i].id] = id[now.id];
47             q.push(a[i]);
48         }
49         else
50         {
51             id[a[i].id] = ++ans;
52             q.push(a[i]);
53         }
54     }
55     cout<<ans<<endl;
56     for(int i = 1; i <= n; i++)cout<<id[i]<<endl;
57     return 0;
58 }