[백준(BOJ) 15589번] Lifegaurds (Silver) 풀이

어떤 구간이 다른 구간을 포함하고 있을 때, 포함되는 구간을 제거하면 최대가 된다.

 

그렇지 않을 경우, 모든 구간이 커버하는 영역의 총 길이를 A라고 하고, 어떤 두 구간도 overlap 되지 않는 가장 짧은 영역의 길이를 B라고 하면, A-B가 답이 된다.

 

왼쪽부터 sweeping 하면서 A와 B를 구하면 O(N)이고, 정렬이 O(NlogN)이므로 총 시간복잡도는 O(NlogN)이 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);

    int N;
    vector<pair<int, int>> se, shift;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int start, end;
        cin >> start >> end;
        se.emplace_back(start, end);
        shift.emplace_back(start, 1), shift.emplace_back(end, -1);
    }

    sort(se.begin(), se.end());
    sort(shift.begin(), shift.end());

    // One contains another.
    bool does_contain = false;
    int max_end = 0;
    for (auto p : se) {
        if (p.second <= max_end) {
            does_contain = true;
            break;
        }
        max_end = p.second;
    }

    int overlaps = 0, last_t = shift.front().first, all_covered = 0, min_gap = 1e9;
    for (auto s : shift) {
        if (overlaps == 1) min_gap = min(min_gap, s.first - last_t);
        if (overlaps >= 1) all_covered += s.first - last_t;
        last_t = s.first;
        overlaps += s.second;
    }

    if (does_contain)
        cout << all_covered;
    else
        cout << all_covered - min_gap;

    return 0;
}