【ACWing】111. 畜栏预定

题目地址：

https://www.acwing.com/problem/content/113/

有N NN头牛在畜栏中吃草。每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。给定N NN头牛和每头牛开始吃草的时间A AA以及结束吃草的时间B BB，每头牛在[ A , B ] [A,B][A,B]这一时间段内都会一直吃草。当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式：
第1 11行：输入一个整数N NN。
第2.. N + 1 2..N+12..N+1行：第i + 1 i+1i+1行输入第i ii头牛的开始吃草时间A AA以及结束吃草时间B BB，数之间用空格隔开。

输出格式：
第1 11行：输出一个整数，代表所需最小畜栏数。
第2.. N + 1 2..N+12..N+1行：第i + 1 i+1i+1行输出第i ii头牛被安排到的畜栏编号，编号是从1 11开始的连续整数，只要方案合法即可。

数据范围：
1 ≤ N ≤ 50000 1≤N≤500001≤N≤50000,
1 ≤ A , B ≤ 1000000 1≤A,B≤10000001≤A,B≤1000000

本质上，问题可以转换为，给定若干闭区间，要求将它们分组，使得同一组内的区间两两不相交，问最少的分组数，和分组方案。思路和证明参考https://blog.csdn.net/qq_46105170/article/details/113734794。代码如下：

#include<algorithm>#include<iostream>#include<queue>usingnamespacestd;constintN=5e4+10;intn;structCow{intid,l,r;}cow[N];intres[N];intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){cow[i].id=i;scanf("%d%d",&cow[i].l,&cow[i].r);}sort(cow+1,cow+1+n,[&](auto&c1,auto&c2){returnc1.l<c2.l;});autocmp=[&](auto&c1,auto&c2){returnc1.r>c2.r;};priority_queue<Cow,vector<Cow>,decltype(cmp)>heap(cmp);intid=0;for(inti=1;i<=n;i++){auto&c=cow[i];if(heap.size()&&heap.top().r<c.l){autoctop=heap.top();heap.pop();res[c.id]=res[ctop.id];}elseres[c.id]=++id;heap.push(c);}printf("%d\n",id);for(inti=1;i<=n;i++)printf("%d\n",res[i]);}

时间复杂度O ( N log ⁡ N ) O(N\log N)O(NlogN)，空间O ( N ) O(N)O(N)。