思路方向
为了实现最小数量的牛围栏,要尽可能的重复使用已经安排过了那些围栏,而对于那些已经安排过了的围栏再利用的前提就是:上一次使用该围栏的牛吃草时间和当前要安排的牛的吃草时间互不干扰,因此这个就成为了破题点。同时还有一个点要考虑,那就是题目所给的数据中牛吃草时间段是无序的,那么若我们不对他进行重新排序的话,就可能导致后面的多个牛和前面的牛本可以共用一个牛围栏,但是由于你没有排序的缘故,出现了漏算的情况,所以要排序
对于牛如何排序,我们回到最初的牛围栏重复使用的前提,时间互不干扰——意味着上一头牛在该围栏吃草的牛的最后时间是小于当前牛的吃草时间的,即两头牛的吃草时间是无交集的,因此我们就可以把牛吃草时间按照开始时间从小到大进行排序,在进行遍历每头牛的同时看之前所有牛的结束吃草时间最小值(可以用小根堆优化),并将共用一个牛围栏的牛放在一起
为什么是最小值呢?
因为要想尽可能的使用牛围栏就从小算起,这样把后面更多的牛围栏给后续的牛用
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> heap;
const int N =5e4 + 10;
int n;
struct C
{
int l, r;
int num;
}c[N];
int s[N], cnt = 1;
bool cmp(C a, C b)
{
return a.l < b.l;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> c[i].l >> c[i].r;
c[i].num = i;
}
sort(c + 1, c + n + 1, cmp);
for(int i = 1; i <= n; i++)
{
if(!heap.size() || heap.top().first >= c[i].l) //若当前没有集合也就是开始时,或者之前所有的牛吃草的结束时间都要大于本牛的开始时间也就意味着两者之间有交集,那么就开一个新的围栏供当前牛使用
{
s[c[i].num] = heap.size();
heap.push({c[i].r, s[c[i].num]});
}
else //若有交集,则本牛继续用那个牛围栏,此时时间就要更新了,因为本来那个牛围栏空余着的时间被当前牛所使用 了
{
auto tem = heap.top();
heap.pop();
s[c[i].num] = tem.second;
heap.push({c[i].r, tem.second});
}
}
cout << heap.size() << endl;
for(int i = 1; i <= n; i++)
cout << s[i] + 1 << endl;
}