1.题目概述
输入样例：
5 1 2 2 4 5 6 7 8 7 9
输出样例：
3
2.代码实现
思路：
- 按区间左端点排序，每次维护一个区间
- 新增区间的三种关系：
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; vector<PII> segs; void push(vector<PII> &segs) //区间合并 { vector<PII> res; sort(segs.begin(),segs.end()); int st=-2e9,ed=-2e9; for(auto item : segs) { if(ed<item.first) { if(ed!=-2e9) res.push_back({st,ed}); st=item.first; ed=item.second; } else ed=max(ed,item.second); } if(st!=-2e9) res.push_back({st,ed}); //加入最后一个区间 segs = res; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { int l,r; scanf("%d%d",&l,&r); segs.push_back({l,r}); } push(segs); cout<<segs.size(); return 0; }
