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

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

bool cmp(const cow &a1,const cow & a2){//數(shù)組排序，開始時(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ù)組排序，還原原來輸入時(shí)的編號(hào)順序
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);//按照開始時(shí)間大小排序
int result = 1;
queue<int> nowr ;//記錄空閑牛棚編號(hào)的隊(duì)列
priority_queue<cow> judge;//以結(jié)束時(shí)間優(yōu)先的優(yōu)先級(jí)隊(duì)列
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)先級(jí)隊(duì)列并更新
    }

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;
}