BOJ 11000 강의실 배정

www.acmicpc.net/problem/11000

11000번: 강의실 배정

강의실 배정 문제다. 어떻게 하면 최대한 적은 강의실을 사용해서 모든 강의를 할 것인지를 찾아내면 된다.

처음에는 회의실 배정 문제랑 비슷한 문제인 것 같아서 강의 종료 시점을 기준으로 정렬해서 제출했는데 틀렸다.

찾아보니 priority_queue를 사용해서 시작시간을 기준으로 해결해야 한다.

큐는 최소 힙으로 선언해주고 큐에는 종료시간만 삽입한다.

 

대략적인 접근방법은 이렇다.

• 벡터에 pair로 시작시간, 종료시간을 입력받는다
• 시작시간을 기준으로 정렬하고 priority_queue에 첫 번째 종료시간을 삽입한다(이때 큐는 최소 힙)
• 큐의 top이(종료시간이) 배열의 시작시간보다 같다면 큐에 삽입
• 아니라면 큐를 pop 하고 삽입

이러면 이후에 남아있는 priority_queue의 사이즈가 정답이 된다.

 

간단한 예시로

 

6

 

1 3

2 5

7 8
7 11

4 12

9 10

 

이 들어간다면

 

 

 

이런 식으로 빨강, 초록, 파랑 회의실의 종료 시점이 들어갈 것이다.

 

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

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, x, y;
	cin >> n;
	priority_queue<int, vector<int>, greater<>> pq;
	vector<pair<int, int>> ar;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		ar.push_back({ x,y });
	}
	sort(ar.begin(), ar.end());

	pq.push(ar[0].second);
	for (int i = 1; i < n; i++) {
		if (pq.top() > ar[i].first) pq.push(ar[i].second);
		else {
			pq.pop();
			pq.push(ar[i].second);
		}
	}
	cout << pq.size() << endl;

	return 0;
}