poj 3190 优先队列

poj3190

思路：
因为问是最少要多少个地方才能安排好所有牛，所以对于牛按照开始时间升序 开始时间一样按结束时间升序
我们考虑把每头牛丢进去，当前这头牛进去的话 把这头牛的开始时间与已经进去的牛的最早结束的时间比较，如果结束时间＞最早结束的时间 那么就是一头牛代替另一头牛进去，那么自然所需要的个数就不变，如果开始时间≤最早结束的时间，那么我们需要新开辟一个地方，让这头牛进去。
综上所述 我们是需要一个可以支持自动排序 、插入、删除的数据结构 自然是优先队列了

维护一个以结束时间的小根堆即可

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int s,e,id;
}a[500005];
struct nodee
{
    int e,id;
    friend bool operator<(nodee a,nodee b){      ///以结束时间的小根堆
        return a.e>b.e;
    }
};
bool cmp(node a,node b){

    return a.s==b.s?a.e<b.e:a.s<b.s;
}
int ans[500005];
int main(){
    
    ios::sync_with_stdio(0);
    int n;
    while(cin>>n){

        for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].e,a[i].id=i;
        sort(a+1,a+1+n,cmp);///对牛的开始和结束时间进行升序
        priority_queue<nodee> q;
        q.push({a[1].e,1});
        ans[a[1].id]=1;
        int cnt=1;
        for(int i=2;i<=n;i++){
            nodee now=q.top();
             if(now.e>=a[i].s){///最先结束的时间 ≥ 当前的开始时间 要新加一个
                ans[a[i].id]=++cnt;
                q.push({a[i].e,cnt});
            }
            else///一头牛出来 当前这头进去
            {
                q.pop();
                ans[a[i].id]=now.id;///存这头牛进入的编号
                q.push({a[i].e,now.id});
            }
        }
        cout<<cnt<<endl;
        for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    }
    return 0;
}