백준 15593 Lifeguards (USACO January 2018 Bronze 2번)

문제 링크: https://www.acmicpc.net/problem/15593

15593번: Lifeguards (Bronze)

한명씩 차례대로 뺀 상태에서 커버되는 시간을 구하고, 그 값들의 최대값을 구하면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int N, s[101], e[101], t[1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> s[i] >> e[i];
        for(int j = s[i]; j < e[i]; j++) t[j]++;
    }
 
    int ans = 0;
    for(int i = 0; i < N; i++) {
        for(int j = s[i]; j < e[i]; j++)
            t[j]--;
 
        int cnt = 0;
        for(int j = 0; j <= 1000; j++)
            if(t[j]) cnt++;
        ans = max(ans, cnt);
 
        for(int j = s[i]; j < e[i]; j++)
            t[j]++;
    }
 
    cout << ans << '\n';
    return 0;
}