수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 에 시작해서 에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 가 주어진다. ()
강의실의 개수를 출력하라.
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;
}