给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤10^5
−10^9≤ai≤bi≤10^9
输入样例：
1. 3 2. -1 1 3. 2 4 4. 3 5
输出样例：
2
思路：有两种解法
解法一：常规思路
这里用heap来存放max_r,heap中存放r的个数也就是heap.size()就等价于需要开的组数
完整代码：
#include <iostream> using namespace std; #include <algorithm> #include <queue> typedef long long ll; const int N=1e5+10; int n; struct range{ ll l,r; bool operator<(const range &w)const { return l<w.l; } }range[N]; int main(){ cin>>n; for(int i=0;i<n;i++) { cin>>range[i].l>>range[i].r; } sort(range,range+n); priority_queue<int,vector<int>,greater<int>> heap; for(int i=0;i<n;i++) { auto r=range[i]; if(heap.empty()||heap.top()>=r.l)heap.push(r.r); else { heap.pop(); heap.push(r.r); } } cout<<heap.size(); }
解法二：
输入区间数和每个区间的端点。
对区间的起点和终点分别进行排序，这样可以方便地比较区间之间的关系。
遍历区间，如果当前区间的起点小于等于前一个区间的终点，则说明它们有交集，需要放在同一组，增加组数。
否则，更新前一个区间的终点为当前区间的终点，表示当前区间和前一个区间没有交集。
输出最终的组数。
自己模拟一下就清晰了
完整代码（带注释）：
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int N=1e5+10; ll a[N],b[N]; int n,ans; int main(){ cin>>n; for(int i=0;i<n;i++)cin>>a[i]>>b[i]; sort(a,a+n); sort(b,b+n); int j=0; for(int i=0;i<n;i++) { if(a[i]<=b[j]) ans++; else j++; } cout<<ans; }
