[BOJ] 강의실 1374번 C++

 

 

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

 

접근 방식

 

우선순위 큐를 이용해 간단하게 최소 강의실 개수를 구할 수 있다.

먼저, 모든 강의 시작 시간, 강의 종료 시간을 벡터에 저장한 후 오름차순으로 정렬한다.

이후, 벡터를 반복문을 통해 확인하며 현재 우선순위 큐(최소힙)를 확인한다.

1. 우선순위 큐가 비어있다면 현재 원소의 강의 종료 시간을 큐에 넣는다.

2. 우선순위 큐가 비어있지 않다면

2-1. 현재 우선순위 큐의 가장 첫번째 요소, 즉 최소 힙의 top이 강의 시작시간보다 작은지 확인하고, 작다면 최소힙의 top을 pop 해준다.

2-2. 위를 확인하고 다시 큐에 혀재 원소의 강의 종료 시간을 넣는다.

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N; cin>>N;
    vector<pair<int,int>> v(N);

    for(int i=0; i<N; i++) {
        int x; cin>>x>>v[i].first>>v[i].second;
    }

    sort(v.begin(), v.end());
    priority_queue<int, vector<int>, greater<>> q;

    for(auto c : v) {
        if(q.empty()) q.push(c.second);
        else {
            if(q.top() <= c.first) q.pop();
            q.push(c.second);
        }
    }

    cout<<q.size();

}