'알고리즘/탐욕(Greedy)'에 해당되는 글 1건

회의실 배정 - BOJ 1931

www.acmicpc.net/problem/1931

회의실의 시작 시간과 끝 시간이 주어졌을때 가장 많은 회의를 할 수 있는 회의수를 구하는 문제입니다. 아래와 같은 입력에 대해서 4개의 회의를 진행할 수 있고 최대로 회의를 할 수 있는 수입니다.

회의할 수 있는 시간은 (1 4), (5 7), (8 11), (12 14)가 될 수 있겠습니다.

입력

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

출력

4

소스 코드

회의실 문제는 탐욕 알고리즘을 적용하는 유명한 문제 중 하나인데요.

여기서 가장 먼저 시작하는 회의를 선택해서는 이 답을 찾을 수 없습니다. 예를 들어 회의가 (0 5), (3 4), (4 5), (6 8), (5 10) 이렇게 5개가 예정이 되어있다고 가정하겠습니다.  가장 먼저 시작하는 회의를 고른다면 만약 (0 5), (5 10)이 됩니다.하지만 (3 4), (4 5), (6 8)로 3개로 더 많은 회의를 진행할 수 있지요.

혹은 가장 짧게 회의를 진행하는 순서대로 회의를 진행하면 답을 찾을 수 있을 것 같긴하지만 다음과 같은 상황((1 7), (5 9), (8 13)이 있는 회의)이 발생한다면 오답이 발생하게 됩니다. 

(5 9)가 가장 짧은 회의로 그것을 먼저 선택했을때는 1개밖에 진행할 수가 없고, 나머지를 선택하면 2개를 진행할 수 있게 됩니다. 이것도 역시 해답은 아니군요.

결론은 항상 가장 먼저 끝나는 회의 먼저 배정해주면 됩니다. 그리고 겹치는 회의를 제거하면 되지요. 즉, 아래와 같은 순서대로 회의를 지정해주면 됩니다.

1. 현재 남아있는 회의들 중 가장 먼저 회의가 끝나는 것부터 출력하고 가장 마지막에 끝난 회의라고 하여 lastFinishedTime에 끝난 시간을 기록합니다.

2. 그리고 이 회의와 겹치지 않는 가장 먼저 끝나는 회의를 선택하여 출력합니다. 그러려면 lastFinishedTime보다 그 다음 진행할 회의의 시작 시간보다 작거나 같아야합니다.

3. 이 과정을 배열이 끝날때까지 반복합니다.

입력은 가장 먼저 끝나는 순서대로 주어지지 않을 수 있으니, 끝나는 순서로 정렬하는 과정이 필요합니다. 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<pair<int, int> > arr;
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int start, end;
		scanf("%d %d", &start, &end);

		//정렬은 첫번째 기준으로 정렬이 되기 때문에 end, start 로 pair
		arr.push_back({ end,start });
	}


	//끝나는 순서대로 정렬
	sort(arr.begin(),arr.end());

	int ret = 1;
	int lastFinishedTime = arr[0].first;
	for (int i = 1; i < arr.size(); i++) {
		int nextStartTime = arr[i].second;
		if (lastFinishedTime > nextStartTime) continue;
		lastFinishedTime = arr[i].first;
		ret++;
	}

	printf("%d\n", ret);
}

BOJ 1931 회의실 배정 문제를 풀어보았습니다. 이 문제는 탐욕 알고리즘과 정렬 알고리즘이 섞인 문제였습니다.