백준 1931. 회의실 배정

알고리즘 중급 문제 중 710 - 그리디 알고리즘

회의실 배정

1. 간단 설명

---

회의실 예약의 회전율을 높여야한다

회의 시작시간과 종료시간이 주어졌을 때, 최대 사용할 수 있는 회의의 개수를 출력하는 문제

2. 예시

---

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

(1,4), (5,7), (8,11), (12,14) 회의를 하면 4번 할 수 있다

3. 알고리즘

---

무엇을 정렬할지가 이 문제의 포인트다

회의 시작시간, 회의 종료시간, 실제 회의 시간 등 다양한 데이터가 있다

이 중 가장 빨리 끝나는 회의순으로 정렬하는게 정답이다

잘 설명된 글이 있어 링크

1. 회의 개수 N과 회의 정보들을 입력받는다
2. 회의가 끝나는 시간 순으로 오름차순 정렬한다. 만약 끝나는 시간이 같다면 시작 시간 순으로 오름차순 정렬한다
3. 맨 앞의 데이터를 꺼낸다.
	- 회의 개수에 1을 추가하고, 언제 끝나는지 확인한다
	- 다음 회의를 꺼내서 시간이 겹치는지 체크한다. 겹치면 넘어간다
4. 이를 모든 회의를 볼때까지 반복하면 된다

4. 소스코드

---

Vector를 이용하여, 직접 정렬하는 버전

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

using namespace std;

int n;
vector< pair<int, int> > meeting;

bool compare(pair<int, int> front, pair<int, int> back) {
	// 1. 끝나는 시간 오름차순
	// 2. 시작 시간 오름차순 
	if (front.second < back.second) return true;
	if (front.second > back.second) return false;
	return front.first < back.first;
}

void Input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;
		meeting.push_back(make_pair(start, end));
	}
}

int main() {
	// freopen_s(new FILE*, "test.txt", "r", stdin);
	Input();

	// 끝나는 시간 순으로 정렬
	sort(meeting.begin(), meeting.end(), compare);

	// 그리디 
	int cnt = 0;
	int time = 0; // 이전회의의 끝나는 시간을 저장

	for (int i = 0; i < meeting.size(); i++) {
		// 이전 회의의 끝나는 시간
		if (meeting[i].first >= time) {
			time = meeting[i].second;
			cnt++;
		}
	}

	cout << cnt++;

	return 0;
}

우선순위 큐를 이용해 정렬하는 버전

#include <iostream>
#include <queue>

using namespace std;

int N;

struct Meeting {
	int start;
	int end;
};

struct cmp {
	bool operator()(Meeting a, Meeting b) const {
		if (a.end == b.end) return a.start > b.start;
		return a.end > b.end;
	}
};

priority_queue<Meeting, vector<Meeting>, cmp> pq;

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int start, end;
		cin >> start >> end;
		pq.push({ start, end });
	}
}

int main() {

	Input();

	int time = 0;
	int cnt = 0;

	while (pq.size() > 0) {
		Meeting now = pq.top();
		pq.pop();

		if (time <= now.start) {
			time = now.end;
			cnt++;
		}

	}

	cout << cnt;

	return 0;
}

우선순위 큐는 기본적으로 최대값을 우선으로 하는 최대 힙 형태로 동작한다

그러므로, 구조체 비교 함수를 오버로딩할 때 구현에 주의해야한다

오름차순으로 구현하고자 한다면, 작은값이 높은 우선순위를 가지도록 반대로 정의해야한다

struct cmp {
	bool operator()(Meeting a, Meeting b) const {
		if (a.end == b.end) return a.start > b.start;
		return a.end > b.end;
	}
};

우선순위 큐의 비교 구현 부분을 보면 벡터 버전과는 반대로 구현되어있는 것을 볼 수 있다

종료 시간이 작을수록 높은 우선순위를 가져야 하므로 반대로 정의했다

이러한 구조체 비교는 여러 문제에서 많이 사용되니 잘 알아둘 것!!