[C++] 백준 19598 최소 회의실 개수 [Gold5]

풀이

큐를 사용해서 문제를 해결하고 싶었는데, 아이디어가 생각나지 않아서 다른 분의 힘을 빌렸다.

아이디어는,

1. 우선순위 큐를 사용해서 회의의 끝 시간을 저장하고 새로 들어오는 회의의 시작시간을 비교한다.

2. 큐에 들어있는(회의실 사용중인) 끝 시간이 새로 들어온 회의의 시작 시간보다 작거나 같을 경우 새로 들어오는 회의를 바로 시작할 수 있으므로 기존의 회의를 pop 해준다.

3. 이렇게 종료시간이 새로 들어온 회의의 시작 시간보다 작거나 같은 회의는 모두 회의실을 반납(pop) 한다.

4. 회의실 반납이 끝나면 새로 들어온 회의를 push 한다.

5. 큐에는 아직 끝나지 않은 회의와, 새로 시작한 회의가 있게 된다. 

6. 큐 크기를 answer에 업데이트 하고, 큐 크기의 최대 값이 문제의 정답이 된다. 

 

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

using namespace std;
using ll = long long;
/*
*   N개의 회의를 모두 진행할 수 있는 최소 회의실의 개수는?
*   한 회의실에서 동시에 두 개 이상의 회의가 시작될 수 없다, 끝나는 동시에 시작가능 
*   1. 시작 시간 기준 오름차순 정렬
*   2. 가장 처음 회의의 끝 시간을 우선순위 큐 push
*   3. 현재 회의의 시작시간과 앞의 모든 회의의 끝 시간 비교
*   4. 앞의 회의 끝 시간이 현재 회의의 시작시간보다 작다면 pop 
*   5. pop 할 수 없으면 현재 회의의 끝 시간 push
*   6. 현재 점유된 회의실 수 업데이트
*/
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    freopen("19598.txt", "r", stdin);

    int N;
    ll start, end;
    cin >> N;
    vector<pair<ll, ll>> v(N);

    for (int i = 0; i < N; i++) {
        cin >> start >> end;
        v[i] = make_pair(start, end);
    }

    sort(v.begin(), v.end());

    // for (auto i:v) {
    //     cout << i.first << " " << i.second << endl;
    // }
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    pq.push(v[0].second);
    int ans = 1;
    for (int i=1; i<v.size(); i++) {
        while (!pq.empty() && pq.top() <= v[i].first)
            pq.pop();
        pq.push(v[i].second);
        ans = max(ans, (int) pq.size());
        
    }
    cout << ans << endl;

    return 0;
}