题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<long long,long long> PLL;
vector<PLL> section;  //保存输入的区间
vector<PLL> res;  //保存合并后的区间

int main()
{
    int i,n;
    long long l,r,st,ed;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>l>>r;
        section.push_back(pair<int,int>(l,r));
    }
    sort(section.begin(),section.end()); //按照区间的第1个端点排序
    int count=0;
    st=section[0].first;
    ed=section[0].second;
    for(i=1;i<section.size();i++)
    {
        if(section[i].first>ed)  //当前区间与上一个区间无交集
        {
            res.push_back(pair<int,int>(st,ed));
            st=section[i].first;
            ed=section[i].second;
        }
        else //当前区间与上一个区间有交集
        {
            //修正上一个区间端点
            st=min(st,section[i].first);
            ed=max(ed,section[i].second);
        }
    }  //for循环后最后一个区间没有加入res数组
    res.push_back(pair<int,int>(st,ed));
    cout<<res.size();

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla