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

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

 

코드

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

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef pair<int, int> pi;

vector<pi> v;
priority_queue<int, vector<int>, greater<int>> pq;
int n;

int main() {
	FASTIO;
	cin >> n;
	v.resize(n);
	for (int i = 0, s, e; i < n; i++) {
		cin >> s >> e;
		v[i] = { s, e };
	}

	sort(v.begin(), v.end());
	pq.push(v[0].second);

	for (int i = 1; i < n; i++) {
		if (v[i].first >= pq.top()) pq.pop();
		pq.push(v[i].second);
	}

	cout << pq.size();
	return 0;
}

설명

수업의 시작 시간, 종료 시간을 입력받고 빠른 수업 순으로 정렬해줍니다. 이후 가장 빠른 시간에 시작하는 수업의 종료시간을 우선순위 큐에 넣습니다. 이후부터는 반복문을 돌면서 이후 빠른 수업대로 확인합니다. 헌재 큐의 top에 있는 수업의 종료시간이 수업 시작시간보다 클 경우에는 해당 강의실에서 수업을 할 수 있으므로 pq.pop을 합니다. 모든 경우에 대해서는 pq.push를 해서 강의실 개수를 증가시킵니다.

 

최종적으로 남아 있는 우선순위 큐의 원소 개수가 곧 강의실 개수이니 이를 출력합니다.

 

느낀 점

우선순위 큐를 이용해서 풀었습니다.