11000번 강의실 배정

문제 링크

강의실 배정

문제 풀이

끝나는 시간을 기준이 아닌 시작하는 시간을 기준으로 정렬하여 탐색한다. 처음부터 탐색하면서 비어있는 강의가 있으면 그 곳에서 시작하고, 아니면 새로 추가하는 식으로 수행한다. 이때 minheap에 탐색한 강의의 끝나는 시간을 넣고, 만약 minheap의 top()인 가장 빨리 끝나는 강의와 현재 강의의 시작하는 시간과 비교하여 top()에 저장된 값이 작거나 같다면 이 강의실이 비어있는 것과 같으므로 minheap에서 pop한다.

구현

#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
vector<pair<int, int>> meeting;
priority_queue<int, vector<int>, greater<int>> pq; // minheap

int solve() {
    pq.push(0);
    for (int i = 0; i < N; ++i) {
        if (pq.top() <= meeting[i].first) pq.pop();
        pq.push(meeting[i].second);
    }
    return pq.size();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; ++i) {
        int s, e;
        cin >> s >> e;
        meeting.push_back(make_pair(s, e));
    }
    sort(meeting.begin(), meeting.end());
    cout << solve();
    
    return 0;
}