[백준 11000번 / C++] 강의실 배정

<priority_queue> 자료구조

---

그리디 문제이다 

방 배정을 하기 위한 최소 값을 구하기 위해서는 각 강의에서의 종료시간과 시작시간이 겹치지 않으면 된다. 

 

#접근방법 

1. pair 벡터를 생성하여 시작 시간과 종료 시간을 저장한다. 
2. 오름차순으로 정렬한다. 
3. priority_queue를 최소힙으로 만들어주고 종료시간을 push한다 (종료시간의 최소값이 top에 위치)
4. for문을 돌면서 priority_queue에 top에 위치한 값보다 같거나 큰 시작시간의 강의가 들어오게되면 queue에 들어있는 top 값을 pop 해준다. 
5. 반복문이 다 돌게 되면 queue의 사이즈가 최소 방의 개수이다. 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std; 
int n; 
int main() {
	cin >> n;
	vector <pair<int, int>> v(n);
	priority_queue <int, vector<int>, greater<int>>q; //최소힙
	for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end()); 
	q.push(v[0].second); 
	for (int i = 1; i < v.size(); i++) {
		if (q.top() <= v[i].first) {
			q.pop();
		}
		q.push(v[i].second);
	}
	cout << q.size(); 
}

 

11000번: 강의실 배정