[C++] 백준 1931번: 회의실배정

문제 바로가기

 

⛳문제에서 요구하는 것⛳

1. 한 개의 회의실이 있다.

2. N개의 회의가 주어진다.

3. 각 회의를 서로 겹치지 않게 배치한다.

4. 배치할 수 있는 회의의 최대 개수를 찾아보자.

 

🧨주어진 조건🧨

1. 1 ≤ N ≤ 100,000

2. 0 ≤ 시작시간 ≤ 종료시간 ≤ 2³¹-1

3. 한 회의가 끝남과 동시에 다음 회의가 시작될 수 있다.

4. 회의의 시작과 종료가 같을 수 있다.

 

✨내가 처음에 생각한 풀이✨

1. vector<pair<int, int>>에 각 회의를 담는다.

2. 시작, 종료 우선순위로 오름차순 정렬한다.

3. 각 회의에 대해서 다음(4~6)을 수행한다.

  4. 선택된 회의의 다음부터 끝 중 ⅰ. 시작시간 ≥ 현재 회의의 종료시간 ⅱ. 가장 빠른 종료시간인 회의를 찾는다.

  5. 만약, 그런 회의가 없다면 최대 회의의 개수를 최신화하고 탐색을 종료한다.

  6. 찾은 회의를 다음 회의로 지정한다.

4. 최대 회의의 개수를 출력한다.

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

#define EL "\n"

using namespace std;

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

	int N;
	cin >> N;

	vector<pair<int, int>> meetings;

	for (int i = 0; i < N; i++) {
		int start, finish;
		cin >> start >> finish;
		meetings.push_back(make_pair(start, finish));
	}

	sort(meetings.begin(), meetings.end());

	cout << EL;
	int max_length = 1;
	int cursor = 0;
	for (auto outset = meetings.begin(); outset != meetings.end(); ++outset) {
		
		int length = 0;
		auto meeting = outset;
		while (meeting != meetings.end()) {
			length++;

			// Step 1. find next meeting
			//	- start after this meeting finished
			//	- earliest finished meeting
			auto next = meetings.end();
			for (auto iter = meeting + 1; iter != meetings.end(); ++iter) {
				if (iter->first >= meeting->second) {
					if (next == meetings.end())
						next = iter;
					else if (iter->second < next->second)
						next = iter;
				}
			}

			// Step 2. if next is empty, update the length
			if (next == meetings.end())
				if (length > max_length)
					max_length = length;

			// Step 3. decide the next meeting
			meeting = next;
		}
	}

	cout << max_length << EL;

	return 0;
}

 

👓결과와 문제점 분석👓

결과: 시간초과

1. 그리디 알고리즘에 대한 이해가 부족하다.

2. 정렬 방법이 잘못 됐다.

3. 불필요한 반복이 많다.

 

🎯옳은 풀이🎯

👁‍🗨 그리디 알고리즘에 대해서
그리디 알고리즘은 최적의 답을 찾기 위해, 순간마다 최적의 선택을 하는 방법을 말한다.
예를 들어, 한 지점에서 다른 지점으로 가는 경로 중 비용을 최소로하는 경로를 찾을 때,
각 지점마다 비용이 최소인 경로를 택해서 답을 내는 경우가 그리디 알고리즘에 해당한다.
이 문제에서는, 선택할 수 있는 회의 중 종료 시간이 가장 빠른 회의를 다음 회의로 선택하는 방식으로 이를 적용할 수 있다.

1. 각 회의의 시작과 종료를 입력 받는다.

2. 시작시간 기준으로 오름차순 정렬을 한다.

3. 종료시간 기준으로 오름차순 정렬을 한다.

  ※ 이렇게 정렬하면, 다음 회의를 선택할 때 빠르게 선택할 수 있다. 왜냐하면, ⅰ. 시작시간 ≥ 현재 회의의 종료시간를 찾으면 첫 번째로 찾게되는 요소가 ⅱ. 가장 빠른 종료시간인 회의가 된다. 아래 표를 참고하면 알기 쉽다.

처음 선택되는 요소는 가장 빨리 종료되는 회의다. 아래에서는 (1, 3)이 된다. 그 다음 요소는 위의 조건을 만족하는 회의인데, 우측 기준으로 정렬돼 있으면 순서대로 확인하다가 조건을 만족하는 요소가 있으면 그 요소가 최적의 선택이 된다.

따라서 아래에선 (1, 3) → (4, 5) → (5, 6)이 회의를 최대로 배치하는 경우다.

만약, 좌측처럼 정렬돼 있으면 가장 빨리 종료되는 회의를 찾는데에도 오래 걸리며, 그 다음 회의를 선택할 때도 두 조건을 만족시키는 요소를 찾기위해 남은 요소를 모두 확인해야하는 문제가 있다.

시작시간, 종료시간 순서대로 오름차순	종료시간, 시작시간 순서대로 오름차순
(0, 5)	(1, 3)
(1, 3)	(2, 3)
(1, 6)	(0, 5)
(2, 3)	(4, 5)
(4, 5)	(1, 6)
(5, 6)	(5, 6)

 

🎈답안🎈

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

#define EL "\n"

using namespace std;

typedef struct Meeting {
	int begin;
	int end;
} Meeting;

int compare_begin(Meeting lhs, Meeting rhs) {
	return lhs.begin < rhs.begin;
}

int compare_end(Meeting lhs, Meeting rhs) {
	return lhs.end < rhs.end;
}

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

	int N;
	cin >> N;

	vector<Meeting> meetings;

	for (int i = 0; i < N; i++) {
		Meeting meeting;
		cin >> meeting.begin >> meeting.end;
		meetings.push_back(meeting);
	}

	sort(meetings.begin(), meetings.end(), compare_begin);
	sort(meetings.begin(), meetings.end(), compare_end);

	int length = 1;
	auto meeting = meetings.begin();
	for (auto iter = meetings.begin() + 1; iter != meetings.end(); ++iter) {
		if (iter->begin >= meeting->end) {
			meeting = iter;
			length++;
		}
	}

	cout << length << EL;

	return 0;
}