区间和并—acwing

题目一：区间和并

803. 区间合并 - AcWing题库

代码

PII存储区间，排序左端点。first存左端点。

遍历区间，考虑边界情况。每访问一个区间，都更新为最右边的那个端点（max)

是否合并区间通过，该区间，与上一个区间ed（最右边端点）比较。右边则，res++;

#include<bits/stdc++.h>
using namespace std;using PII = pair<int,int>;
int n;
const int N = 1e5+10;
PII a[N];int main() {cin >> n;for(int i = 0; i < n; i ++) {int l, r;cin >> l >> r;a[i] = {l,r};}int res = 0;sort(a,a+n);int ed = -2e9;for(int i = 0; i < n; i ++) {if(a[i].first>ed) {res ++;}ed = max(ed,a[i].second);}cout << res << endl;return 0;
}

代码2（模板）

// yxc 区间和并模板代码
#include<bits/stdc++.h>using namespace std;
using PII = pair<int,int>;const int N = 1e5+10;int n;
vector<PII> a;void solve(vector<PII> &a) {vector<PII> res;sort(a.begin(), a.end());// 区间边界初始值int st = -2e9, ed = -2e9;for(auto x : a) {if(ed<x.first) {// 开始的边界处理if(st != -2e9) res.push_back({st,ed});st = x.first, ed = x.second;}else ed = max(ed,x.second);}// 最后的区间 边界//防空if(st!=-2e9) res.push_back({st,ed});a = res;
}int main() {cin >> n;for(int i = 0; i <= n; i ++) {int l, r;cin >> l >> r;a.push_back({l,r});}solve(a);cout << a.size() << endl;return 0;
}