畜栏预定
题意
有 N 头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定 N 头牛和每头牛开始吃草的时间 A 以及结束吃草的时间 B，每头牛在 [A,B] 这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
思路
将问题转换为，将一些区间分配到一些数轴上，同一数轴上的任意两个区间没有交集，问最少需要多少个数轴。
将区间按左端点升序排序，同时用一个优先队列（小根堆）存储每个数轴上区间右端点的最大值，那么堆顶就是右端点最小的数轴，如果最小的右端点都和待入的区间有交集，那么放在其他的数轴自然也会有交集。 如果当前区间能插入到某个数轴，那么更新此数轴的右端点为当前区间的右端点，否则只能开辟一个新的数组，并将其右端点设置为当前区间的右端点。
最后统计优先队列的大小即为最终答案。
代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 5e4 + 10; int n; struct Node { int l; int r; int idx; bool operator<(Node x) const { return l < x.l; } }node[N]; int res[N]; priority_queue<PII, vector<PII>, greater<PII>>q; //小根堆 void solve() { cin >> n; for (int i = 1; i <= n; ++i)cin >> node[i].l, cin >> node[i].r, node[i].idx = i; sort(node + 1, node + 1 + n); for (int i = 1; i <= n; ++i) { if (!q.size())q.push({ node[i].r ,1 }), res[node[i].idx] = 1; else { if (q.top().first >= node[i].l) { q.push({ node[i].r ,q.size() + 1}); res[node[i].idx] = q.size(); } else { auto t = q.top(); q.pop(); t.first = node[i].r; res[node[i].idx] = t.second; q.push(t); } } } cout << q.size() << endl; for (int i = 1; i <= n; ++i)printf("%d\n", res[i]); } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
