[백준 1374번] 강의실 (C++)

문제링크 : https://www.acmicpc.net/problem/1374

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, A, B, C; //강의 갯수, 강의 번호, 시작 시간, 종료 시간
int cnt=1; //최소 강의실
vector<pii>v;
priority_queue<int, vector<int>, greater<int>> pq;

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

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> A >> B >> C;
        v.push_back({B, C});
    }

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

    for(int i=0; i<v.size(); i++)
    {
        auto [s, e] = v[i];
        if(pq.empty()) pq.push(e);
        else
        {
            if(pq.top() > s) cnt++; //강의실 추가
            else pq.pop(); //기존 강의실 이용
            pq.push(e);
        }
    }

    cout << cnt;
    
    return 0;
}

 

시작시간과 종료시간을 벡터에 담고 해당 벡터를 시작 시간 순으로 정렬해준다.

이후 우선 순위 큐를 이용하여 종료 시간 기준으로 값을 push 해준다.

 

만약 현재 우선 순위 큐의 top(직전 종료시간)이 시작 시간보다 크다면 같은 강의실 사용이 불가한 케이스이므로 강의실을 추가하고, top(직전 종료 시간)이 시작 시간보다 작거나 같다면 강의실을 이어서 사용가능하므로 기존 top 값을 삭제한다.

두 케이스 모두 새롭게 종료시간이 할당되었으니, 우선 순위 큐에 현재 종료 시간 값을 push한다.

 

벡터 크기 만큼 이를 반복하여 수행하며, 이렇게 카운팅한 강의실 갯수를 출력해주면 된다.