백준[1374] 강의실

문제 설명

문제 링크

http://icpc.me/1374

1374번: 강의실

풀이

이 문제는 관찰을 잘한다면 풀 수 있다.

모든 수업에 대해서 시작하는 시간과 끝나는 시간을 정렬해서 가지고 있을 때, 만약 지금 보는 수가 수업이 시작하는 수라면 필요한 강의실이 하나 더 필요할 것이다. 반대로 지금 보고 있는 수가 끝나는 시간이라면 필요한 강의실이 하나 줄어들 것이다.

예를 들어, 1~4까지 하는 수업과 2~5까지 하는 수업이 있고 이 수들을 정렬하여 1 2 4 5라는 수를 가지고 있을 때, 1 때는 시작을 하기 때문에 필요한 강의실이 하나 늘고 2 때도 필요한 강의실이 하나 늘고 4시가 되면 수업이 하나 끝나기 때문에 필요한 강의실이 하나 줄고 5시가 되면 하나 더 줄 것이다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
using p = pair<int, bool>;

vector<p> v;

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        v.push_back({b, true});
        v.push_back({c, false});
    }
    sort(v.begin(), v.end());
    int cnt = 0, ans = 0;
    for (auto &k : v) {
        if (k.second) cnt++;
        else cnt--;
        ans = max(ans, cnt);
    }
    printf("%d", ans);
}