https://www.acwing.com/problem/search/1/?csrfmiddlewaretoken=A6hJmK9QIKhI2BjKpv9ngRnfmmlSDTEY6DjbNvDxBtLwn1nSLHtW0NrLCd6KKoSn&search_content=%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6
一、简述 区间合并 就是将坐标轴中两个存在交集 的区间合并 成一个 区间 。
二、 思想 1.将所有 区间 按左端点从小到大排序 2.从左到右遍历每个 区间 ，把有交集 的区间合并 如果前一个右端点 小于下一个左端点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
int l,m;
int res;
void merge(vector<PII> &segs){
res = l+1;
sort(segs.begin(),segs.end());
int st = -2e9,ed=-2e9+10;
for(auto seg : segs){
if(ed<seg.first){
if(st!=-2e9){
res=res-(ed-st+1);
}
st=seg.first;
ed=seg.second;
}else{
ed = max(ed,seg.second);
}
}
if (st != -2e9) res=res-(ed-st+1);
}
int main()
{
cin>>l>>m;
while(m--){
int a,b;
cin>>a>>b;
segs.push_back({a,b});
}
merge(segs);
cout<<res<<endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
int res1,res2;
int n;
void merge(vector<PII> &segs){
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9+10;
for(auto seg:segs){
if(ed<seg.first){
if(st!=-2e9){
res2=max(res2,seg.first-ed);
res1=max(res1,ed-st);
}
st=seg.first;
ed=seg.second;
}else{
ed=max(ed,seg.second);
}
}
if(st!=-2e9){
res1=max(res1,ed-st);
}
}
int main()
{
cin>>n;
while(n--){
int a,b;
cin>>a>>b;
segs.push_back({a,b});
}
merge(segs);
cout<<res1<<" "<<res2<<endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
PII segs[N];
int n,res;
int main()
{
cin>>n;
for(int i =0;i<n;i++){
cin>>segs[i].first>>segs[i].second;
}
sort(segs,segs+n);
for(int i =0;i<n;i++){
int st=-1,ed=-1,sum=0;
for(int j =0;j<n;j++){
if(i!=j){
if(ed<segs[j].first){
if(st!=-1) sum+=ed-st;
st=segs[j].first;
ed=segs[j].second;
}
else ed = max(ed,segs[j].second);
}
}
if(st!=-1) sum+=ed-st;
res=max(res,sum);
}
cout<<res<<endl;
return 0;
}
|