[BOJ] 11000. 강의실 배정 ✔

11000. 강의실 배정

1. 문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 $S_{i}$에 시작해서 $T_{i}$에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, $T_{i} ≤ S_{j}$ 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

2. 입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 $S_{i}, T_{i}$가 주어진다. ($1 ≤ S_{i} < T_{i} ≤ 10^9$)

3. 출력

강의실의 개수를 출력하라.

4. 풀이

Python

import heapq

N = int(input())

times = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x : x[0])
# 수업 시작 시간과 종료 시간을 시작 시간을 기준으로 정렬하여 저장

heap = []
for time in times:
    if heap and heap[0] <= time[0]:
        heapq.heappop(heap) # 힙의 맨 앞 수업의 종료 시간이 time의 시작 시간보다 빠를 경우 pop
    heapq.heappush(heap, time[1])
    
print(len(heap))

C++

using namespace std;
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
typedef pair<int, int> P;

bool cmp(P a, P b)
{
    if (a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    
    vector<P> time(N);
    for (int i = 0; i < N; ++i) cin >> time[i].first >> time[i].second;
    sort(time.begin(), time.end(), cmp);
       
    int result(1);
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(time[0].second);
    for (int i = 1; i < N; ++i)
    {
        pq.push(time[i].second);
        // time[i]의 수업 시작 시간이 pq 맨 앞의 종료 시간보다 빠를 경우 +1
        if (time[i].first < pq.top()) ++result;
        // 아니라면 그 수업의 강의실을 이용
        else pq.pop();
    }
    
    cout << result;
}