11000

최소 강의실의 개수를 구하는 문제.

먼저 수업들을 시작 시간을 기준으로 다시 정렬을 해두자. class[]

그리고 현재 강의실중 가장 수업이 빨리 끝나는 강의실을 관리하는 자료구조를 가지고 있다고 하자. (우선순위 큐를 이용해서 관리하는게 좋다)

정렬된 배열 class[] 에 있는 i번째 수업을 내가 추가하고자 한다면

현재 강의실 중에서 가장 수업이 빨리 끝나는 강의실에 추가하는 것이 최적의 경우일 것이다.

만약 i번째 수업의 시작시간이 가장 수업이 빨리 끝나는 강의실의 끝나는 시간보다 더 일찍 시작한다면, i번째 수업은 반드시 강의실을 추가해서 들을 수밖에 없다. 다른 강의실들은 가장 수업이 빨리 끝나는 강의실보다 더 늦게 끝날 것이 분명하기 때문이다.

우선순위큐와 정렬을 적당히 활용해서 풀면 쉽게 풀수 있다.

 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

vector<int> rooms;
vector<pair<int, int> > c;

int main(){
	
	int n, from, to;
	scanf("%d", &n);

	for(int i=0; i<n; i++){
		scanf("%d %d", &from, &to);
		c.push_back(make_pair(from, to));
	}
	sort(c.begin(), c.end());

	priority_queue<int > pq;
	pq.push(0);
	for(int piv=0; piv < c.size(); piv++){
		int cur_finish = -pq.top();
		if(c[piv].first < cur_finish){
			pq.push(-c[piv].second);
		}
		else{
			cur_finish = -c[piv].second;
			pq.pop();
			pq.push(cur_finish);
		}
	}

	printf("%d\n", pq.size());
	return 0;
}