[C++] 백준 11000 - 방 배정

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

11000번: 강의실 배정

<알고리즘 분류>

   - 정렬

   - 우선순위 큐(Priority Queue)

<풀이> 

  1. 백준 사이트에 나와 있는 예제 입력을 활용하여, 그림으로 쉽게 표현했다. 자세한 것은 그림을 확인하길 바란다. 

<코드>

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

using namespace std;

int N;
pair <int, int> p[200000];

int main(){

    cin >> N;
    for (int i=0; i<N; i++){
        int x, y;
        cin >> x >> y; 
        p[i].first = x;
        p[i].second = y;
    }
    sort(p, p+N);
    priority_queue <int, vector<int>, greater<int>> pq;

    pq.push(p[0].second);

    for (int i=1; i<N; i++){
       if (p[i].first < pq.top()){ //top에 있는 것과 시간이 겹친다면(강의실추가)
            pq.push(p[i].second);
        }
        else{ //겹치지 않는다면 
            pq.pop();
            pq.push(p[i].second);
        }
    }

    cout << pq.size();
}