題目鏈接：https://vjudge.net/problem/POJ-3190
意思：每個牛在某個區(qū)間工作，需要占用一個牛棚婿牍，問至少需要準(zhǔn)備多少牛棚，并給出一個分配方案
思路：貪心加上優(yōu)先級隊列的題惩歉，需要注意等脂，下一頭牛開始時間必須是上一頭牛結(jié)束時間+1才能用同一個牛棚。我采用的是用一個優(yōu)先級隊列（結(jié)束時間優(yōu)先）撑蚌，一個數(shù)組排序（開始時間優(yōu)先）上遥，然后一個普通隊列（記錄哪些牛棚編號可以用）。掃描每一頭牛争涌，首先將優(yōu)先級隊列中所有結(jié)束時間比當(dāng)前牛開始時間早的彈出粉楚，并將對應(yīng)牛棚編號壓入普通隊列（就是更新一遍對于該牛當(dāng)前哪些牛棚可以用），緊接著先判斷隊列是否為空亮垫，如果為空則需要一個新牛棚模软，否則可以用空閑的原來有的牛棚，最后把當(dāng)前牛的信息壓入優(yōu)先級隊列饮潦，循環(huán)掃描所有牛的數(shù)據(jù)即可得到燃异。
代碼：
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

struct cow{
int start;//開始時間
int end;//結(jié)束時間
int num;//給牛的編號
int qq;//牛所用牛棚的編號
bool operator < (const cow & a)const{//優(yōu)先級隊列，結(jié)束時間小的優(yōu)先
return end > a.end;
}
};

bool cmp(const cow &a1,const cow & a2){//數(shù)組排序继蜡，開始時間小的優(yōu)先
if(a1.start!=a2.start)
return a1.start<a2.start;
return a2.end<a2.end;
}

bool cmp2(const cow &a1,const cow & a2){//數(shù)組排序回俐，還原原來輸入時的編號順序
return a1.num<a2.num;
}

int n;

int main(){
while(scanf("%d",&n)==1){
vector<cow> all;
cow now;
for(int i=0;i<n;i++){
scanf("%d%d",&now.start,&now.end);
now.num = i+1;
all.push_back(now);
}
sort(all.begin(),all.end(),cmp);//按照開始時間大小排序
int result = 1;
queue<int> nowr ;//記錄空閑牛棚編號的隊列
priority_queue<cow> judge;//以結(jié)束時間優(yōu)先的優(yōu)先級隊列
all[0].qq = 1;
judge.push(all[0]);

    for(int i=1;i<n;i++){
        while(all[i].start>judge.top().end){//更新一遍當(dāng)前可用牛棚的狀態(tài)
            nowr.push(judge.top().qq);
            judge.pop();
        }
        if(nowr.size()==0){//先判斷是否為空，為空則增加最小牛棚數(shù)量
            result++;
            all[i].qq = result;
        }
        if(nowr.size()!=0){//不為空則用已有的空閑牛棚
            all[i].qq = nowr.front();
            nowr.pop();
        }
        judge.push(all[i]);//將當(dāng)前牛狀態(tài)壓入優(yōu)先級隊列并更新
    }

printf("%d\n",result);

sort(all.begin(),all.end(),cmp2);
for(int i = 0;i<n;i++){
printf("%d\n",all[i].qq);
}
}
return 0;
}