这题是母题 区间分组 的一个应用。
思路在这里
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 50010;
int n;
int id[N]; //牛的编号 映射到 牛所属的围栏号
pair<PII,int> cow[N]; //牛的进食时段、牛的编号
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
cow[i] = {{l,r},i};
}
sort(cow,cow + n); //按进食时间段左端点排序
int num = 1;
priority_queue<PII,vector<PII>,greater<PII>> heap; //存围栏已占有时间的右边界和围栏编号
heap.push({cow[0].first.second, num}); //至少存在一个围栏,先把第一只牛加进去
id[cow[0].second] = 1;
for(int i=1;i<n;i++)
{
int l = cow[i].first.first, r = cow[i].first.second, cowNum = cow[i].second;
if(l > heap.top().first) //若这只牛能放到这个围栏
{
int t = heap.top().second; //记录一下这个围栏的编号
heap.pop();
heap.push({r, t}); //更新围栏信息
id[cowNum] = t; //记录这只牛所属围栏号
}
else //若这只牛不能放进任何围栏
{
heap.push({r, ++num}); //分配新的围栏给他
id[cowNum] = num; //记录这只牛所属围栏号
}
}
cout<<heap.size()<<endl;
for(int i=0;i<n;i++) cout<<id[i]<<endl;
return 0;
}