[baekjoon 1374] 강의실 (그리디, 우선순위 큐) (C++)

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

1374번: 강의실

강의실의 이용 시작 시간, 종료 시간이 주어지고 이 예약 정보들을 감당하는 최소한의 강의실 개수를 구해야 한다.

 

처음엔, 누적 합처럼 모든 예약 시간을 배열에 저장한 다음에 겹치는 시간의 최대 개수를 구하려고 했지만

예약 시간의 범위가 10억이라서 불가능이라고 생각했다.

 

이 문제는 우선순위 큐를 이용해야 하는데, 이런 유형의 문제가 명확하게 생각하기 힘들어서 어렵다고 느껴진다.

 

1. 최소한의 강의실 개수로 많은 예약을 감당하려면 빨리 시작하고 빨리 끝나는 강의를 우선적으로 넣어야 한다.

2. 그 이후에 시작 예정인 강의가 현재 진행 중인 강의와 겹치면, 이때 강의실을 늘려야 한다.

3. 만약, 시작 예정인 강의의 시작 시간이 진행 중인 강의의 끝나는 시간 이후라면 (겹치지 않는다면), 해당 강의실에서 진행하면 된다.

 

따라서 두 가지의 정보를 정렬해서 진행해야 하는데

 

1. 강의 예약 정보  - vector에서 pair로 갖고 있을 것이다.

- 시작하는 시간, 끝나는 시간 모두 오름차순으로 정렬해야 빨리 시작하는 강의 순으로, 그중에서도 빨리 끝나는 강의를 진행시킬 수 있다.

 

2. 현재 강의실에서 진행 중인 강의들의 끝나는 시간 정보 - 우선순위 큐에서 int로 갖고 있을 것이다.

- 끝나는 시간 정보를 오름차순으로 갖고 있어야, 가장 빨리 끝나는 강의와 비교해서 강의실 사용 여부를 알 수 있기 때문이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, room, from, to, answer = 1;

typedef pair<int, int> pii;

vector<pii> v;
priority_queue<int, vector<int>, greater<int>> lastTime;

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> room >> from >> to;
		v.push_back({ from, to });
	}
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		int startTime = v[i].first;
		int endTime = v[i].second;

		if (lastTime.empty()) {
			lastTime.push(endTime);
		}
		else {
			if (lastTime.top() > startTime) { // 아직 안 끝난 경우 회의실이 없다.
				answer++;
			}
			else { // 빈 회의실로 들어가면 된다.
				lastTime.pop(); // 끝난 강의는 없애준다.
			}
			lastTime.push(endTime); // 어떤 경우에서든지 새롭게 시작한 강의 정보를 저장한다.
		}
	}
	cout << answer;
}

그래서 결국 "제일 일찍 끝나는 강의의 시간"을 이용해서

해당 시간보다 느리면 "이미 그 강의는 끝난 강의이므로" 해당 강의실을 이용 & 끝난 강의 정보 삭제

해당 시간보다 빠르면 "해당 강의와 겹치므로" 강의실을 증설

- 제일 일찍 끝나는 강의보다 빠르면 다른 강의실에서 진행 중인 강의(더 늦게 끝나는)와도 겹친다는 의미이므로

그리고 기존 강의실을 이용하던지, 증설하던지 새롭게 강의가 시작한 것이므로 우선순위 큐에 끝나는 정보를 push 해준다.