（https://www.acwing.com/problem/content/805/）
给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
思路：贪心。总的区间为n，每次合并一个区间，n--。注意处理边界问题：不能枚举到最后一个
#include <iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; typedef pair<int,int>pll; vector<pll> all; int main() { int n; cin >> n; for(int i=1;i<=n;i++) { int l,r; cin >> l >> r; all.push_back({l,r}); } sort(all.begin(),all.end()); int ans=n; for(int i=0;i<all.size()-1;i++)//不能枚举到最后一个 { if(all[i].second>=all[i+1].first) { ans--; all[i+1].first=all[i].first; all[i+1].second=max(all[i+1].second,all[i].second); } } cout <<ans << endl; return 0; }