题解 P2082 【区间覆盖(加强版)】

按Ctrl加w会AC · 2018-02-26 23:06:07 · 题解

贪心

将 l 排序，然后从左到右维护 max\_R 表示已经贪心到的最右端的边界+1，如果当前的右边界大于等于 max\_R 就加上区间长度，减去重复覆盖的累计答案更新 max\_R

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x7FFFFFFFFFFFFFFFll
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int n;
struct SEG{
    ll l,r;
    bool operator <(const SEG v)const{return l<v.l;}
} A[MAXN];
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>A[i].l>>A[i].r;
    sort(A+1,A+1+n);
    ll max_R=-INF,ans=0;
    for (int i=1;i<=n;i++)
        if (max_R<=A[i].r) ans+=A[i].r-max(max_R,A[i].l)+1,max_R=A[i].r+1;
    cout<<ans<<'\n';
    return 0;
}