[ 백준 11000 ] 강의실 배정 (c/c++)

 

 

[ 문제 요약 ]

S에 시작해서 T에 끝나는 수업 N개가 주어질 때 강의실을 최소로 쓰는 경우의 강의실 개수를 출력한다.

 

 

[ 문제 풀이 ]

1. 수업 N개를 받아 먼저하는 수업 순으로 정렬한다.

2. 처음 하는 수업은 무조건 할 수 있으므로 우선순위 큐에 그 수업이 끝나는 시간을 넣는다.

3. 만약 어떤 수업이 우선순위 큐의 top값, 즉 가장 먼저 끝나는 수업의 시간보다 시작하는 시간이 느리다면 그 수업의 새 강의실이 필요하지 않다.

4. 만약 그렇지 않다면 그 강의는 새로운 강의실이 필요하므로 우선순위 큐에 넣는다.

5. 모든 수업에 대해서 하고 난 뒤 우선순위 큐의 크기가 답이 된다.

 

 

[ 소스 코드 ]

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

int N;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    cin >> N;
    for (int i=0; i<N; i++){
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
    sort(v.begin(), v.end());

    pq.push(v[0].second);
    for (int i=1; i<N; i++){
        if (v[i].first >= pq.top()){
            pq.pop();
            pq.push(v[i].second);
        }
        else {
            pq.push(v[i].second);
        }
    }

    cout << pq.size();
    
    return 0;
}

 

 

[ 주의할 점 ]

코드를 구현하는 것은 쉬웠지만 문제 풀이를 떠올리는 것이 어려웠다.