[1374번] 강의실

www.acmicpc.net/problem/1374

1374번: 강의실

문제

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

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

 

입력

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

 

출력

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

 

풀이

먼저 입력에서 강의번호, 강의 시작 시간, 강의 종료 시간을 입력받는데, 강의 번호는 입력만 받고 이 이후로는 별로 쓸모가 없다. 형식상으로만 일단 입력을 받는다. 그리고 강의 시작 시간과 종료 시간을 vector<pair<int, int>> lectures 배열에 입력을 받는다. 입력을 받고 난 후, sort를 하면 시작시간을 기준으로 오름차순으로 정렬될 것이다.  

sort한 벡터배열을 기준으로 우선순위 큐 pq에 할당한다.

근데 진행중인 강의의 종료시간이 새 강의의 시작시간보다 더 크다면 cnt++하고, 그게 아니라면 pq.pop()을 해서 빼낸다.  

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> pq;		//최소 힙(오름차순)

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

	int n, num, cnt = 0;
	cin >> n;
	vector<pii> lectures(n);

	for (int i = 0; i < n; i++) {
		cin >> num >> lectures[i].first >> lectures[i].second;		//강의번호(=num)은 어차피 필요없음. 그냥 형식상 입력받는다.
	}

	sort(lectures.begin(), lectures.end());		//시작시간을 기준으로 오름차순으로 정렬

	for (int i = 0; i < n; i++) {
		if (pq.size() > 0) {
			if (pq.top().first > lectures[i].first)
				cnt++;
			else
				pq.pop();
		}
		else
			cnt++;
		pii lec;
		lec.first = lectures[i].second;
		lec.second = lectures[i].first;
		pq.push(lec);
	}

	cout << cnt;

	return 0;
}