백준 BOJ 11000 C++ [강의실 배정]

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> lectures;
    for (int i = 0; i < n; ++i) {
        int s, e;
        cin >> s >> e;
        lectures.push_back({s, e});
    }
    sort(lectures.begin(), lectures.end());  // 시작 시간을 기준으로 오름차순 정렬
    priority_queue<int, vector<int>, greater<int>> pq;  // 종료 시간이 빠른 강의가 우선 순위(종료 시간을 기준으로 오름차순 정렬)
    pq.push(lectures[0].second);  // 먼저 첫 강의의 종료 시간을 우선 순위 큐에 삽입
    for (int i = 1; i < n; ++i) {  // 모든 강의를 탐색하며
        if (pq.top() <= lectures[i].first) {  // 지금 가장 빨리 끝나는 강의의 종료 시간과 현재 강의의 시작 시간을 비교하여
            pq.pop();  // 현재 선택한 강의를 뒤에 이어서 진행가능하면(앞의 강의 시간과 겹치지 않는다면) 앞의 기존 강의의 종료시간을 큐에서 제거
        }
        // 강의 시간이 겹치는 경우 새로운 강의실이 추가적으로 필요
        pq.push(lectures[i].second);  // 현재 강의의 종료 시간을 우선 순위 큐에 삽입
    }
    // 우선 순위 큐에서 빠지는 경우는 해당 강의 뒤로 강의가 진행되는 경우이므로
    // 우선 순위 큐에는 각 강의실의 마지막 강의의 종료 시간이 들어있음
    // 따라서 우선 순위 큐의 크기는 강의가 겹치지 않도록 하는 최소 강의실의 개수이다.
    cout << pq.size() << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}