[BOJ] 최소 회의실 개수 19598번 C++

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최소 회의실 개수를 출력한다.

 

접근 방식

 

최소힙으로 구현된 우선순위 큐로 간단하게 풀었다

먼저 회의시간 배열을 vector에 저장한 후 회의 시작시간에 대해 오름차순 sort 를 진행해주었다

 

그리고 최소힙 우선순위 큐를 생성하고

배열을 돌면서 만약 우선순위 큐가 비었다면 회의 종료시간, 회의 시작 시간 순으로 넣어준다 (회의 종료시간으로 최소힙을 구현하기 위함)

우선순위 큐가 비지 않았다면 현재 top에 종료 시간보다 현재 배열의 시작시간이 크거나 같으면 pq.pop해준다

그리고 다시 회의 시간을 넣어준다

이렇게 하면 최소 회의실 개수는 pq size 가 된다

 

 

코드

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

int N;
vector<pair<int,int>> v;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
int main() {
    cin>>N;
    for(int i=0; i<N; i++) {
        int s,e; cin>>s>>e;
        v.push_back({s,e});
    }
    sort(v.begin(), v.end());

    for(auto c : v) {
        if(pq.empty()) pq.push({c.second, c.first});
        else {
            int en = pq.top().first;
            if(en <= c.first) pq.pop();
            pq.push({c.second, c.first});
        }

    } 
    cout<<pq.size();
}