题目描述
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B,每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
样例
输入样例:
5
1 10
2 4
3 6
5 8
4 7
输出样例:
4
1
2
3
2
4
算法1
(贪心加排序) $O(nlogn)$
这里详细见y总的基础课贪心问题的区间分组问题
这里主要就是多了一个维护的问题,在排序后要维护未排序前的一些东西。这里的是排序后原来标记的奶牛的位置会发生变化,比如原来的第五头奶牛是[4,7],经过排序后就变到了4的位置,所以就要想想怎么维护这个原来的位置,注意到存储区间用的是结构体range,可以多加一个成员来存储原来的位置,这样就可以在后面标记位置的时候记的是原来的位置,参见代码中的t.w.
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N =50010;
typedef pair<int,int>PII;
int n,cnt=1;
int a[N];
struct range{
int l,r,w;
bool operator<(const range &w)const{
return l<w.l;
}
}range[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r,i};
}
sort(range,range+n);
priority_queue<PII,vector<PII>,greater<PII>>heap;//PII存的是最大右端点和这组的桩位
for(int i=0;i<n;i++){
auto t=range[i];
if(heap.empty()||heap.top().first>=t.l) {
heap.push({t.r,cnt});
a[t.w]=cnt++;
}
else{
int k=heap.top().second;
heap.pop();
a[t.w]=k;
heap.push({t.r,k});
}
}
printf("%d\n",heap.size());
for(int i=0;i<n;i++) printf("%d\n",a[i]);
return 0;
}