acwing.111.畜栏预定 有N头牛在畜栏中吃草。 每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。 给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。 当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。 求需要的最小畜栏数目和每头牛对应的畜栏方案。 #include #include #include #include #include #include using namespace std; typedef pair<int,int> pa; const int N=50050; int n; int id[N]; pair<pa,int> cow[N]; int main() { cin>>n; for(int i=0;i<n;i++) { cin>>cow[i].first.first>>cow[i].first.second; cow[i].second=i; } sort(cow,cow+n); priority_queue<pa,vector,greater> heap; for(int i=0;i<n;i++) { if(heap.empty()||heap.top().first>=cow[i].first.first) { pa stall={cow[i].first.second,heap.size()}; id[cow[i].second]=stall.second; heap.push(stall); } else { auto stall=heap.top(); heap.pop(); stall.first=cow[i].first.second; id[cow[i].second]=stall.second; heap.push(stall); } } cout<<heap.size()<<endl; for(int i=0;i<n;i++) cout<<id[i]+1<<endl; return 0; } 一种贪心算法 首先将牛按照开始时间排序 采用 如果能放入已有畜栏 就放入 放不了就新建的贪心算法 用小根堆将n2 算法 降低到nlogn cow的pair储存每个奶牛的吃草开始结束时间和其编号（因为要用sort进行排序） 对于每个stall维护他的结束时间和他的编号（也是总size） 操作就是遍历每一个牛，如果放入已有畜栏，则维护畜栏 ，如果没有 新建 维护 放入小根堆。
