畜栏预定贪心

有 N 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草&＃xff0c;所以可能会需要多个畜栏。

给定 N 头牛和每头牛开始吃草的时间 A 以及结束吃草的时间 B&＃xff0c;每头牛在 [A,B] 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时&＃xff08;包括端点&＃xff09;&＃xff0c;这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式
第 1 行&＃xff1a;输入一个整数 N。

第 2…N&＃43;1 行&＃xff1a;第 i&＃43;1 行输入第 i 头牛的开始吃草时间 A 以及结束吃草时间 B&＃xff0c;数之间用空格隔开。

输出格式
第 1 行&＃xff1a;输入一个整数&＃xff0c;代表所需最小畜栏数。

第 2…N&＃43;1 行&＃xff1a;第 i&＃43;1 行输入第 i 头牛被安排到的畜栏编号&＃xff0c;编号是从 1 开始的 连续 整数&＃xff0c;只要方案合法即可。

数据范围
1≤N≤50000,
1≤A,B≤1000000
输入样例&＃xff1a;
5
1 10
2 4
3 6
5 8
4 7
输出样例&＃xff1a;
4
1
2
3
2
4

#include
using namespace std;
typedef pair<int,int> PII;
const int N&＃61;50010;
int n;
int id[N];
pair<PII,int> cows[N];
int main(){cin >>n;for(int i&＃61;0;i<n;i&＃43;&＃43;){cin >> cows[i].first.first >>cows[i].first.second;cows[i].second&＃61;i; //利用每头牛儿特殊的地方&＃xff0c; 给每头牛儿编号&＃xff0c;方便下面数组操作该头牛儿&＃xff1b; }sort(cows,cows&＃43;n); // 按牛儿开始吃草时间排序&＃xff1b;priority_queue <PII,vector<PII>,greater<PII>>heap; //建立小根堆;for(int i&＃61;0;i<n;i&＃43;&＃43;) { // 贪心,区间组合问题;if(heap.empty()||heap.top().first >&＃61;cows[i].first.first){ // 建立新畜栏&＃xff1b;PII stall &＃61;{ cows[i].first.second,heap.size()};id[cows[i].second]&＃61;stall.second; // 记录这头牛儿在哪个畜栏吃草&＃xff1b;heap.push(stall); // 将新建立的畜栏进堆&＃xff1b;}else { // 如果这头牛儿可以在其他畜栏吃草PII stall&＃61;heap.top(); heap.pop();stall.first&＃61;cows[i].first.second;//将该畜栏的右端点更新为该头牛儿的吃草结束时间&＃xff1b;id[cows[i].second]&＃61;stall.second; //记录这头牛儿在哪个畜栏吃草&＃xff1b;heap.push(stall); // 将更新后的该畜栏入堆&＃xff1b;}
}cout << heap.size() <<endl;for(int i&＃61;0;i<n;i&＃43;&＃43;) cout << id[i]&＃43;1 << endl;return 0;
}
//妙用pair &＃43; 数组的方式记录每头牛儿吃草的畜栏号