题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
PII section[110];

bool cmp(PII a,PII b)
{
    return a.first<b.first;
}

int main()
{
    int L,M,i,l,r,curl,curr;
    long sum=0;
    cin>>L>>M;
    for(i=0;i<M;i++)
    {
        cin>>l>>r;
        section[i].first=l;
        section[i].second=r;
    }

    sort(section,section+M,cmp);  //按照区间左端点从小到大排序
    curl=section[0].first;
    curr=section[0].second;
    for(i=1;i<M;i++)
    {
        if(section[i].first<=curr)  //区间有交集,更新区间左右端点
        {
            //curl=min(curl,section[i].first);
            curr=max(curr,section[i].second);

        }
        else
        {
            sum+=curr-curl+1; //计算之前并集的长度
            curl=section[i].first;
            curr=section[i].second;
        }
    }


        sum+=curr-curl+1;

    cout<<L+1-sum;
}

算法2

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

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla