poj3190区间类贪心＋优先队列

题意：每个奶牛产奶的时间为A到B，每个奶牛产奶时要占用一间房子，问n头奶牛产奶共需要多少房子，并输出每头奶牛用哪间房子

分析：这题就是一个裸的贪心，将奶牛按开始时间进行排序即可，但考虑一下数据范围，我们可以用一个优先队列来进行维护，在优先队列中我们按照奶牛的结束时间最小构造小顶堆，然后判断新进来的元素的开始时间是否比最小的结束时间大，若是，加入队列，修改队列，若不是，加入对列，并且计数加1

注意自定义类型的优先队列的维护方法。详见：http://blog.sina.com.cn/s/blog_4e5157120100vn7b.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int maxn=50050;
//注意自定义类型在优先队列中的用法
typedef struct P
{
    int start,over,id;
    friend bool operator<(P a,P b)
    {
        return a.over>b.over; //小顶堆
    }
}P;
P point[maxn];
bool cmp(P a,P b)
{
    return a.start<b.start;
}
int t[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&point[i].start,&point[i].over);
            point[i].id=i;
        }
        memset(t,0,sizeof(t));
        sort(point,point+n,cmp);
        priority_queue<P> que;
        int r=0; //统计个数
        que.push(point[0]);
        t[point[0].id]=++r;
        for(int i=1;i<n;i++)
        {
            P node=que.top();
            if(node.over<point[i].start){
                t[point[i].id]=t[node.id];
                que.pop();
                que.push(point[i]);
            }
            else{
                t[point[i].id]=++r;
                que.push(point[i]);
            }
        }
        cout<<r<<endl;
        for(int i=0;i<n;i++)
            printf("%d
",t[i]);
    }
    return 0;
}