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

문제

19598번: 최소 회의실 개수

풀이

그리디, 우선순위 큐

 

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

위의 문제와 풀이가 같은 문제

코드

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

using namespace std;

vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

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

    int N;
    cin >> N;

    int answer = 0;

    for (int i = 0; i < N; ++i)
    {
        int start, end;
        cin >> start >> end;

        v.push_back(make_pair(start, end));
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < N; ++i)
    {
        int current_start = v[i].first;
        int current_end = v[i].second;

        if (!pq.empty())
        {
            // 가장 빨리 끝나는 수업이 현재 시작하는 강의보다 빨리 끝난다면 같은 강의실을 사용할 수 있다.
            if (current_start >= pq.top())
            {
                pq.pop();
            }
        }

        pq.push(current_end);

        answer = max(answer, (int)pq.size());
    }

    cout << answer;

    return 0;
}