[백준 / BOJ] C++ 11000 강의실 배정

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

11000번: 강의실 배정

풀이

우선순위 큐와 vector를 이용하였다.

 

vector에 시작시간과 종료시간을 넣은 후 오름차순으로 정렬한다.

이후 우선순위 큐에 오름차순으로 정렬된 종료시간을 저장하고, 이후 종료시간과 두번째 저장된 시작시간을 비교한다.

 

종료 시간보다 시작시간이 작은 경우는, 다른 강의실을 사용해야하기에 우선순위 큐에 넣어주고,

예외 상황에는 동일 강의실을 쓰기에, pop 이후 다시 push를 해준다.

 

Code

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

using namespace std;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    int N; 
    cin >> N;

    vector<pair<int, int>> time(N);
    for (int i = 0; i < N; i++)
        cin >> time[i].first >> time[i].second;

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

    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(time[0].second);

    for (int i = 1; i < N; i++) 
    {
        if (time[i].first < pq.top())
            pq.push(time[i].second);
        else 
        {
            pq.pop();
            pq.push(time[i].second);
        }
    }

    cout << pq.size();
}