AcWing 803. 区间合并

网址 https://www.acwing.com/solution/AcWing/content/1590/

题目描述
给定n个区间[l, r]。

合并所有有交集的区间。

输出合并完成后的区间个数。

例如：[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式
第一行包含整数n。

接下来n行，每行包含两个整数 l 和 r。

输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

样例
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3

算法1
(暴力模拟) O(n2)O(n2)
模版题么 简单暴力模拟
抛开输入输出不说
判断 各个区间是否重合
主要是四种情况
1 A区间的起点在B区间的起点终点之间 Bstart Astart Bend Aend
2 A区间起点终点在B区间的起点终点之间 Bstart Astart Aend Bend
反之亦然
3 B区间的起点在A区间的起点终点之间 Astart Bstart Aend Bend
4 B区间起点终点在A区间的起点终点之间 Astart Bstart Bend Aend

但是代码可以归为两种情况判断

int s1 = vp[i].first;
int e1 = vp[i].second;

int s2 = vp[j].first;
int e2 = vp[j].second;

if( (s1>= s2 && s1<= e2) || (s2 >=s1 && s2 <= e1) ){
}
然后进行合并
两者区间合并后就是 起点是两者起点的最小值 终点是两者终点的最大值
代码

merges = min(s1,s2);
mergee = max(e1,e2);

vp[j].first = merges;
vp[j].second = mergee;

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;
const int N= 100100;
vector<pair<int,int>> vp(N,pair<int,int>(-1,-1));

int Merge(int i,int j)
{
    int s1 = vp[i].first;
    int e1 = vp[i].second;

    int s2 = vp[j].first;
    int e2 = vp[j].second;

    int merges = 0;int mergee= 0;

    if( (s1>= s2 && s1<= e2) ||  (s2 >=s1 && s2 <= e1)  ){
        merges = min(s1,s2);
        mergee = max(e1,e2);

        vp[j].first = merges;
        vp[j].second = mergee;
        return 1;
    }

    return 0;
}


int main()
{
    cin >> T;

    for(int i =1 ;i <= T ;i ++){
        cin >> vp[i].first;  cin >> vp[i].second;             
    }
    int mergeCount =0;
    for(int i =1 ; i <=  T;i++){
        for(int j = i+1;j<= T;j++){
            //比较 i j
            int res = Merge(i,j);
            if(res){
               mergeCount++;
               break;
            }
        }
    }

    cout << T - mergeCount << endl;

    return 0;
}

作者：defddr
链接：https://www.acwing.com/solution/AcWing/content/1590/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。