03.05. 회의실 배정[Greedy Algorithm][백준 1931]

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

1931번: 회의실 배정

 

Algorithm classification : Greedy Algorithm

 

03.05.1. Problem

There is one conference room, and we want to create a conference room usage table for N meetings that we want to use. Given a start time and an end time for each meeting I, let's find the maximum number of meetings that can use the conference room without overlapping each meeting. However, once a meeting starts, it cannot be stopped in the middle, and the next meeting may start at the same time as one meeting ends. The start time and end time of the meeting may be the same. In this case, you can think of it as ending as soon as it starts.

 

03.05.2. Input limit

The first line gives the number of meetings N (1 ≤ N ≤ 100,000). From the second line to the N+1 line, the information of each meeting is given, and the start time and end time of the meeting are given with a space between them. The start time and end time are natural numbers less than or equal to 2^31-1 or 0.

 

03.05.3. Output

The first line prints the maximum number of available meetings.

 

03.05.4. Solution

Greedy choice property와 optimal substructure에 해당하는지 고민해보시면 되는데요. 끝나는 시간이 가장 빠른 회의만 선택한다면 최대 갯수의 회의를 구할 수 있습니다. Time slice table을 그려놓고 생각해보시면 됩니다. 보통 귀류법을 사용하면 문제가 optimal substructure에 해당하는지 쉽게 받아들일 수 있습니다.(끝나는 시간이 가장 빠르지 않은 회의를 선택했을 때가 문제의 해답이 될 수 있는가 고민하면 되는 것이죠) 이러한 2개 이상의 Element를 가지는 것을 정렬할 때는 Vector를 사용하면 편합니다. 여기서 끝나는 시간을 기준으로 먼저 정렬하고 그 다음으로 시작하는 시간을 기준으로 정렬해야 함에 유의하시기 바랍니다. 그러면 어떻게 벡터가 pairing되어야 할지 알 수 있습니다.

	for(i = 0; i < n; i++){
		scanf("%d %d", &s, &e);
		v.push_back(pair<int,int>(e,s));
	} 
	sort(v.begin(), v.end());
	int temp = v[0].first; c++;
	for(i = 1; i < n; i++){
		if(temp <= v[i].second){
			c++;
			temp = v[i].first;
		}	
	}

 

이러한 접근이 마음에 들지 않으신다면 Case를 나누어 보시는 것도 하나의 방법일 수 있습니다. 실제로 복잡한 문제는 Case를 모두 나누어보시는 것이 좋은 방법일 수 있습니다. Case를 나누면 어떠한 알고리즘으로 해결해야할지 감이 오는 경우가 많습니다.

 

• Case 1: 가장 빨리 시작하는 경우 
• Case 2: 가장 빨리 끝나는 경우
• Case 3: 시간이 가장 짧은 경우