BOJ)15589 Lifeguards (Silver)

문제: icpc.me/15589

n명의 인원이 1차원 구간을 커버하는 데  이중에서 한 인원을 제외했을 때 커버가능한 최대 구간을 출력하는 문제이다.

전체 구간에서 하나를 제외 하였을 때 최대 구간을 구하면 되므로

하나의 구간에서 다른 구간에 영향을 받지 않고 유일하게 커버되는 구간 중 최솟값을 구하여 전체 구간에서 빼주면 답이 된다.

각각의 구간에서 독립적으로 커버하는 구간은 왼쪽에서 부터, 오른쪽에서 부터 , 두번 스위핑하여 구할 수 있다. 

자세한 설명은 소스코드로 대신하겠다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,x,y;
vector<pair<int,int>> vt;
vector<int> l,r;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        vt.push_back({x,y});
    }
    sort(vt.begin(),vt.end());
    l.assign(n,0),r.assign(n,0);
    int rmax=0;
    for(int i=0;i<n;i++){
        r[i]=rmax;
        rmax=max(rmax,vt[i].second);
    }
    int lmin=1e9;
    for(int i=n-1;i>=0;i--){
        l[i]=lmin;
        lmin=min(lmin,vt[i].first-1);
    }
    int indcover=1e9;
    for(int i=0;i<n;i++){
        int ll=max(vt[i].first,r[i]);
        int rr=min(vt[i].second-1,l[i]);
        if(ll>rr)indcover=0;
        else indcover=min(indcover,rr-ll+1);
    }
    int cover=0;
    int currl=0,currr=-1;
    for(int i=0;i<n;i++){
        if(currr>=vt[i].first)
            currr=max(currr,vt[i].second-1);
        else{
            cover+=(currr-currl+1);
            currl=vt[i].first,currr=vt[i].second-1;
        }
    }
    cover+=(currr-currl+1);
    printf("%d\n",cover-indcover);
    return 0;
}