[BOJ] 강의실_1374 C++ 풀이

문제

N개의 강의가 있고 각 강의의 시작 시간과 끝나는 시간이 주어진다. 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어 지게 하고싶다고 할때 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하라.

입력으로는 첫째줄에 강의의 개수N이 주어지고 둘째 줄 부터 N개의 줄에 걸쳐 각 줄마다 강의 번호, 강의 시작 시간, 강의 종료 시간이 주어진다.

접근방법

방번호는 사실상 문제를 해결하는데 별 도움이 되지 못하기 때문에 활용하지 않았고, 각 강의 시작시간과 끝나는 시간을 시작시간을 기준으로 우선순위 큐 $($pq) 를 사용하여 top부터 오름차순으로 정렬 될 수 있게 입력을 받았다.

pq의 top에 위치한 강의 시작 시간이 빠른 강의 부터 필요한 강의실을 의미하는 우선순위 큐, room에 삽입해 주는데 만약 pq의 강의 시작 시간이 room의 강의 끝나는 시간 보다 크거나 같다면 강의가 끝난후 새로운 강의가 시작되는 것이므로 강의실이 필요하지 않다. 따라서 room을 pop 시켜 줬다.

문제에서 요구하는 것은 필요한 최소 강의실의 수 이므로 우선순위 큐 room에 원소가 가장 많이 존재할 때의 사이즈를 기록해야 하므로 if(Max_room<room.size()) Max_room=room.size();

구현

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

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    priority_queue<pair<int, int>, vector<pair<int,int> >, greater<pair<int, int> > > pq;
    priority_queue<int, vector<int>, greater<int> > room;
    int n, num, s, e;
    int Max_room=1; // 방이 최대로 필요한 시점의 방 갯수
    
    cin>>n;

    for(int i=0; i<n; i++)
    {
        cin>>num>>s>>e;
        pq.push(make_pair(s,e)); // first = 시작시간, second = 끝나는 시간
    }

    room.push(pq.top().second); // room큐에 강의 끝나는 시간 삽입
    pq.pop();

    while(!pq.empty())
    {
        while(!room.empty() && room.top()<=pq.top().first) room.pop();
        room.push(pq.top().second);
        pq.pop();
        if(Max_room<room.size()) Max_room=room.size();
    }

    cout<<Max_room;
    return 0;
}

BOJ_강의실