火烧赤壁

链接

这题的难点在于怎么区分不同区间是否被覆盖

我们可以这么想,我们将左区间定义为1(覆盖值),右区间定义为-1

找到一个cover,让cover加上每个数对应的覆盖值,如果cover为正,那么这个区间为左区间, 为0或者负数,就为右区间

但是如果我们遇到的是

2(1) 5(-1)

3(1) 7(-1)

的话怎么办呢,这样简单相加必然重复,我们发现7-2=(3-2)+(5-3)+(7-5)

这意味着我们可以进行排序,得到2 3 5 7

由覆盖值的正负可知我们可以加到5(7-5),到7时cover为0,不再相加

如果遇到重复的数呢,比如2 5 2 7 6 9

我们可以得到2(1) 2(1) 5(1) 6(1) 7(-1) 9(-1)

不难发现,2要加两次,我们可以将两个2合并,得到2(2)

依此写出代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    vector<pair<ll,ll>>interval(n);
    vector<ll>points;
    for(int i=0;i<n;i++){
        cin>>interval[i].first>>interval[i].second;
        points.push_back(interval[i].first);
        points.push_back(interval[i].second);
    }
    sort(points.begin(),points.end());
    points.erase(unique(points.begin(),points.end()),points.end());
    int m=points.size();
    unordered_map<ll,int>mp(m);
    for(int i=0;i<m;i++){
        mp[points[i]]=i;
    }
    vector<int>diff(m,0);
    for(int i=0;i<n;i++){
        ll l=interval[i].first,r=interval[i].second;
        diff[mp[l]]++;
        diff[mp[r]]--;
    }
    ll cover=0,ans=0;
    for(int i=0;i<m-1;i++){
        cover+=diff[i];
        if(cover>0){
            ans+=points[i+1]-points[i];
        }
    }
    cout<<ans;
}

时间复杂度:O(n log n)

空间复杂度:O(n)