[BOJ] 회의실배정(1931)

[백준(BOJ)] 회의실배정(1931) C++

문제 : BOJ_1931번 회의실배정

문제 설명

그리디 알고리즘

유명한 그리디 문제입니다.
회의실이 하나 있고 N 개의 회의가 있는데,
회의마다 시작 시간과 끝나는 시간이 정해져있고
회의 시간은 겹칠 순 없지만 회의의 끝 시간과 다음 회의의 시작 시간이 겹칠 순 있습니다.
또 한, 시작 시간과 끝 시간이 동일한 경우도 있습니다.
이때 가능한 회의의 최대 개수를 구하는 문제입니다.


Solution

끝나는 시간이 빠른 회의를 선택하면, 뒤에 선택할 수 있는 회의의 수가 늘어나므로,
끝나는 시간대로 정렬하여 그리디하게 회의를 선택하는 것이 문제의 핵심입니다.
끝 시간 순으로 정렬을 하고, 이전 회의의 끝 시간보다 시작 시간이 늦는다면 최대 개수에 추가해 줍니다.

다만, 시작 시간과 끝나는 시간이 동일한 회의는 이전 회의가 어떻든 간에 영향이 없기 때문에, 무조건 추가해 줍니다.


Description

  1. 시간 순으로 정렬을 하기 위해 우선순위큐를 썼습니다.
  2. 자료형이 pair 일 때, 우선순위큐는 앞의 숫자가 기준이므로 {끝 시간, 시작 시간} 으로 push 했습니다.
  3. 중간에 시작 시간과 끝 시간이 같으면 개수를 +1 해주고 다음 큐를 pop 했습니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, result, beforeStartTime, beforeEndTime;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
// 오름차순인 우선순위큐가 필요하므로 greater<> 추가
int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int startTime, endTime;
		cin >> startTime >> endTime;
		pq.push({ endTime,startTime });
		// pair의 첫 번째 인자가 기준 -> 끝 시간, 시작 시간 순으로 push
	}
	while (!pq.empty()) {
		int nowEndTime = pq.top().first;
		int nowStartTime = pq.top().second;
		pq.pop();
		if (beforeEndTime > nowStartTime) continue;
		// 앞 회의의 끝 시간이 지금 회의의 시작 시간보다 늦으면 넘어간다.
		if (nowEndTime == nowStartTime) {
			// 시작 시간과 끝 시간이 같으면 무조건 추가해준다.
			result++;
			beforeStartTime = nowStartTime;
			beforeEndTime = nowEndTime;
			continue;
		}
		result++;
		beforeStartTime = nowStartTime;
		beforeEndTime = nowEndTime;
	}
	cout << result << '\n';
}