백준 19598 최소 회의실 개수 혼내주기

 

한번에 최대 몇개의 회의가 중복되서 진행되는지를 구하면 된다.
회의 시작 시간을 오름차순으로 정렬한 뒤, 매 회의마다 cnt를 증가시키고(새로운 회의) 우큐에 종료시간을 넣는다. 이후 현재 진행중인 회의의 시작 이전에 끝나는 회의를 우큐에서 모두 꺼내고 cnt를 감소시킨다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

pair<int, int> meetings[100000];
int n;

void input() {
    fastio;
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> meetings[i].first >> meetings[i].second;
}

int main() {
    input();
    sort(meetings, meetings+n);

    int cnt = 0, ans = 0;
    priority_queue<int> pq;    
    for(int i = 0; i < n; ++i) {
        cnt++;
        pq.push(-meetings[i].second);
        while(meetings[i].first >= -pq.top()) {
            cnt--;
            pq.pop();
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}