15589, Gold 1

15589번: Lifeguards (Silver)

문제

• $n(1\leq n \leq 10^{5})$명의 근로자가 각각 $[s_{i}, e_{i})$ 구간을 근무한다
• 누굴 해고해야 전체 근로시간이 가장 길까? 이때 근로시간은?

 

$O(nlog\ n)$

어떤사람을 해고했을 때 전체 근로시간을 줄어들 수도 있고 줄어들지 않을수도 있다
줄어든 시간은 해고한 사람만이 맡았던 구간의 크기(고유시간이라 부르자)와 같다

그러면 구하려고 하는것은
(아무도 해고하지 않았을 때 전체 근무시간) - min(고유시간)

먼저, 전체 근무시간은 스위핑(sweeping)을 이용하여 구할 수 있다

이제 각각의 고유시간을 구하자. 먼저 각각의 근로시간을 sort 한다
인접한 두 근무구간은 다음 3가지 경우중 하나이다(주황: pre, 노랑: cur)

i)  cur.start < pre.end 

ii) cur.end < pre.end

iii) pre.end ≤ cur.start

 

따라서 인접한 3개 구간의 관계는 총 9가지 경우로 나뉜다. 그런데 이중 고유시간을 구하기 까다로운 상황이 있다

- next.end < cur.end 

위와같이 노랑색 구간의 고유시간은 인접 구간만으로는 결정되지 않는다
그런데 생각해 보면 위와같은 경우가 있으면 next 근로자를 해고하면 된다
따라서 위와같은 경우가 없는 경우에 한정하여 고유시간을 생각하자

i) next.start ≤ pre.end 

cur 고유시간 = 0

ii) pre.end < next.start

이 경우 cur 의 상태를 4가지로 나눌 수 있는데 이를 한꺼번에 표현하면
cur 고유시간 = min(cur.end, next.start) - max(cur.start, pre.end)

c++

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    vector<pii> v(n+2);
    v[0] = {0, 0}; v[n+1] = {1e9, 1e9};
    loop(i, n) cin >> v[i].first>> v[i].second;
 
    sort(v.begin(), v.end());
 
    bool isinvolved = false;
    for(int i = 2; i <= n; i++){
        if(v[i].second <= v[i-1].second) {
            isinvolved = true;
            break;
        }
    }
 
    int whole = 0, l = -1, r = -1, min_eigen = 1e9;
    loop(i, n){
        auto [s, e] = v[i];
        if(r < s){
            whole += r-l;
            tie(l, r) = v[i];
        }
        else r = max(r, e);
 
        if(v[i-1].second >= v[i+1].first) min_eigen = 0;
        else{
            int cur_eigen = min(v[i].second, v[i+1].first) - max(v[i-1].second, v[i].first);
            if(min_eigen > cur_eigen) min_eigen = cur_eigen;
        }
    }
    whole += r-l;
    cout << (isinvolved ? whole: whole - min_eigen) << endl;
 
    return 0;
}cs

 

python 3

import sys
 
n = int(input())
shift = sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(n)])
shift = [(-1, -1)] + shift + [(int(1e9)+1, int(1e9))]
 
isinclude = False
for i in range(2, n):
    if shift[i][1] <= shift[i-1][1]:
        isinclude = True
        break
 
min_eigen = int(1e9)
whole, l, r = 0, -1, -1
for i in range(1, n+1):
    if r < shift[i][0]:
        whole += r-l
        l, r = shift[i]
    else: r = max(r, shift[i][1])
 
    if shift[i-1][1] < shift[i+1][0]: eigen = min(shift[i][1], shift[i+1][0]) - max(shift[i][0], shift[i-1][1])
    else: eigen = 0
    if min_eigen > eigen: min_eigen = eigen
whole += r-l
 
print(whole if isinclude else whole - min_eigen)cs