[11000]강의실 배정

3. 유의 할 것

- 입력값이 20만개 이므로 logN형 자료구조를 사용해야 한다.

- 나는 시간을 줄이기 위해서 주로 map,set을 사용했는데 set의 경우 균형 이진 트리이므로 검색은 빠르지만 삽입 & 삭제가 느리다. (삽입,삭제는 log(N))

- 우선순위 큐는 Heap을 사용하므로 set보다 더 빠르다. 삽입 삭제도 logN 이므로 따라서 우선순위 큐를 자주 쓰도록 하자.

 

4. 코드

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

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

	int N,s,e;
	vector<pair<int,int> > v;
	cin >> N;
	for(int i=0;i<N;i++) {
		cin >> s >> e;
		v.push_back({s,e});
	}
	sort(v.begin(),v.end());

	priority_queue<int,vector<int>,greater<vector<int>> > q; //강의실 별 끝나는 시간 저장 
	q.push(v[0].second);
	int i =1;
	for(int i=1;i<N;i++) {
	//i번째 수업을 넣을 수 있는 강의실 찾기
	//가장 빨리 끝나는 수업보다 더 일찍 시작하면 강의실 새로 배정
			if( v[i].first < q.top()) {
				q.push(v[i].second);
			}
	// 수업 종료시간 이후에 수업이 시작하면 해당 강의실에서 수업 시작
			else {
				q.pop();
				q.push(v[i].second);
			} 
	}
	cout << q.size();
	return 0;

}