看了一下，貌似是求最大”区间厚度的问题。
大家可以把这个问题想象成活动安排问题
有若干个活动，第i个活动开始时间和结束时间是[SiSi,fifi]，同一个教室安排的活动之间不能交叠，求要安排所有活动，少需要几个教室？
有时间冲突的活动不能安排在同一间教室，与该问题的限制条件相同，即最小需要的教室个数即为该题答案。
我们可以把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减1,在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数。
请大家不要发无意义的评论啦
C++ 代码
#include #include using namespace std; const int N = 100100; int n; int b[2 * N], idx; int main() { scanf (“%d”, &n); for(int i = 0; i < n; i ++) { int l, r; scanf(“%d %d”, &l, &r); b[idx ++] = l * 2;//标记左端点为偶数。 b[idx ++] = r * 2 + 1;// 标记右端点为奇数。 }
sort(b, b + idx); int res = 1, t = 0; for(int i = 0; i < idx; i ++) { if(b[i] % 2 == 0) t ++; else t --; res = max(res, t); } printf ("%d\n", res); return 0;
}
算法分析
贪心决策
从前往后枚举每个区间，判断此区间能否将其放到现有的组中
如果一个区间的左端点比最小组的右端点要小，ranges[i].l<=heap.top() ， 就开一个新组 heap.push(range[i].r);
如果一个区间的左端点比最小组的右端点要大，则放在该组， heap.pop(), heap.push(range[i].r);
每组去除右端点最小的区间，只保留一个右端点较大的区间，这样heap有多少区间，就有多少组。
算法流程
区间分组，在组内区间不相交的前提下，分成尽可能少的组。
而不是尽可能多的组，因为一个区间一组，就是尽可能多组的答案。
等效于把尽可能多的区间塞进同一组，要满足range[i].l > heap.top。
heap 存储的是每个组的最右的端点，由于是小根堆heap.top()是对应的最小的最右点。
那如果遇到，塞不进去的情况呢？
就是heap.top >= range[i].l, 当前区间的左端点比最小的右端点还要小，放到任何一组都会有相交部分。
那就需要新开一组，heap.push(range[i].r).
把所有区间按照左端点从小到大排序
从前往后枚举每个区间，判断此区间能否将其放到现有的组中
heap有多少区间，就有多少组
#include #include #include #include using namespace std; const int N = 100010; int n; struct Range { int l, r; bool operator< (const Range &W)const { return l < W.l; } }range[N]; int main() { scanf(“%d”, &n); for (int i = 0; i < n; i ++ ) { int l, r; scanf(“%d%d”, &l, &r); range[i] = {l, r}; }
sort(range, range + n); priority_queue<int, vector<int>, greater<int>> heap; for (int i = 0; i < n; i ++ ) { if (heap.empty() || heap.top() >= range[i].l){ heap.push(range[i].r); } else { heap.pop(); heap.push(range[i].r); } } printf("%d\n", heap.size()); return 0;
}
Part1:例题
https://www.acwing.com/problem/content/908/
给定 N 个闭区间[ai,bi][ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
Part2:思路
将所有区间按照左端点进行排序
利用小根堆来维护所有组的右端点。
因为判断一个区间q[i]能否放进某个组，条件是li>maxrli>maxr，maxrmaxr指的是组内所有区间中最靠右的右端点，如果这个区间的左端点大于组的右端点，说明没有交集，可以放进这个组里。
所以判断一个区间能否放进之前的组中，条件是li>(maxr)minli>(maxr)min，只要最小的比它小就一定存在，如果最小的都比它大就一定有交集了。所以根本不需要记录组内有哪些区间，只需要把组的最大右端点放进小根堆里，每次用区间的左端点和堆顶元素比较即可。
从前往后遍历每一个区间
首先把第一个区间放进堆里if(heap.empty())
判断当前区间能否放进现有的某个组中
如果不存在这样的组（有交集）p[i].first<=heap.top()，需要新建一个组，直接把区间的右端点放进堆里heap.push(p[i].second)
如果存在这样的组（无交集）p[i].first>heap.top()，可以任意找一个组放进去， 我们每次都找堆顶所在的组，放进去=更新这个组在队中的右端点=heap.top
heap.pop(); heap.push(p[i].second);
（先丢掉原来的右端点，把新的右端点放进去）
Part3:证明
ans:最终答案
cnt:按照给定的贪心算法得到的答案
ans>=cnt
首先cnt一定是合法方案（不一定是最小的），每个组内的区间没有任何交集
ans是所有方案中的最小值，所以ans>=cnt
ans<=cnt
假设枚举到第i个区间时，打算把这个区间放到某个组内，但前cnt-1个组中都有区间与当前区间有交集，说明至少有cnt个区间有公共点lili，所以这cnt个区间一定不会放到同一组中，所以ans>=cnt
Part4:代码
#include #include #include using namespace std; typedef pair<int,int> PII; const int N=1e5+10; PII q[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; q[i]={l,r}; } sort(q,q+n); //默认按照第一元素（左端点排序） priority_queue<int,vector,greater>heap;
for(int i=0;i<n;i++) { if(heap.empty()||[i].first<=heap.top()) heap.push(q[i].second); else { heap.pop(); heap.push(q[i].second); } } cout<<heap.size()<<endl; return 0;
}
