[BOJ] 1374번 강의실 (C++)

https://www.acmicpc.net/problem/1374

1374번: 강의실

 

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

int main() {
	int n;
	vector<pair<int, int>> v;
	priority_queue<int, vector<int>, greater<>> pq;
	
	cin >> n;
	for(int i = 0; i < n; i++){
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({b, c});
	}
	sort(v.begin(), v.end());
	
	for(int i = 0; i < v.size(); i++){
		if(pq.empty()) {
			pq.push(v[i].second);
			continue;
		}
		if(pq.top() <= v[i].first) {
			pq.pop();
		}
		pq.push(v[i].second);
	}
	
	cout << pq.size() << endl;
	return 0;
}

 

벡터에는 입력받은 강의 시작 시간과 종료 시간을 쌍으로 저장한다. (강의 번호는 저장할 필요 없다.)

벡터를 강의 시작 시간 기준으로 오름차순 정렬한다.

 

벡터를 돌며 오름차순 우선순위 큐에 종료 시간을 저장하는데

- 현재 강의 시작 시간이 우선순위 큐 top에 있는 종료 시간보다 같거나 늦으면 같은 강의실을 쓸 수 있으므로 pop하고 현재 강의 종료 시간을 push한다.

- 현재 강의 시작 시간이 우선순위 큐 top에 있는 종료 시간보다 이르면 같은 강의실을 쓸 수 없으므로 강의 종료 시간을 push한다. (강의실 개수 +1)

 

남아있는 pq의 크기가 최소 강의실 개수가 된다.