[알고리즘] 백준 19598 - 최소 회의실 개수

1. 문제

https://www.acmicpc.net/problem/19598

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

2. 입력/출력

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

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

3. 풀이

https://velog.io/@yeju6540/알고리즘-백준-11000-강의실-배정
문제와 똑같은 풀이 방법을 가지고 있다.

1. 회의 시간을 시작 시간이 작은 순서로 정렬
2. 우선순위 큐에 끝나는 시간을 넣음
   • 우선순위 큐의 맨 앞에 있는 시간보다 현재 회의 시작 시간이 클 경우(== 회의실을 이어서 사용 가능) 우선순위 큐에서 Pop 수행 후 끝나는 시간 넣음
   • 아닐 경우(== 새로운 회의실 필요) 바로 큐에 끝나는 시간 넣음

4. 코드

#include <vector>
#include <iostream>
#include <queue>

using namespace std;
int n;


bool compare(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(0);

    vector<pair<int, int>> arr;
    priority_queue<int,vector<int>,greater<int>> room;

    cin >> n;

    for (int i = 0; i < n; i++) {
        pair<int, int> tmp;

        cin >> tmp.first >> tmp.second;

        arr.push_back(tmp);
    }

    sort(arr.begin(), arr.end(), compare);
    
    room.push(arr[0].second);

    for (int i = 1; i < n; i++) {
        if (room.top() <= arr[i].first) {
            room.pop();
        }
        room.push(arr[i].second);
    }

    cout << room.size();
    return 0;

}