[백준 1931번] - 회의실 배정 [그리디 알고리즘의 증명]

 

www.acmicpc.net/problem/1931

1931번: 회의실배정

 

풀이들을 보면서 왜 끝나는 시간에 대해 정렬하는가? 일찍 끝나는 회의부터 배정하는 방법이 최적해가 될 것임을 어떻게 증명할 것인가? 라는 생각들이 들었습니다. 답을 얻으면서 그리디 알고리즘에 대해 깊이 생각해 볼 수 있었습니다.

 

왜 먼저 끝나는 시간에 대해 정렬하는가?

위에 대한 답은 '탐욕법을 적용할 최적의 부분 구조를 만들기 위해서' 라는 결론을 얻었습니다.

이를 이해하기 위해서는 회의실을 배정한다는 행위에 대한 이해도 필요합니다. 회의실을 배정받기 위해서는 기본적으로 이전의 회의가 없거나 끝나 있어야 합니다.

만약 회의실을 시작 시간을 기준으로, 또는 회의 시간을 기준으로 배정한다고 해봅시다. 부분 문제들은 독립되어 있어야 하므로 앞 배정의 자세한 조건들에 영향 받지 않아야 됩니다. 결국은 회의가 끝나야 다른 회의가 들어올 수 있는데 시간 시간, 회의 시간을 기준으로 해버리면 그게 감춰지고 결국 부분 문제들 간에 의존 관계를 만들어 냅니다.

 

 

 

일찍 끝나는 회의부터 배정하는 방법이 최적해가 될 것임을 어떻게 증명할 것인가? 

 

 

위에서 T는 회의를 배정할 수 있는 총 시간을 의미합니다.

만약 e1을 선택하는 경우 남는 시간은  T-e1이 되고 e2를 선택하면 남는 시간은 T-e2입니다. T-e2만큼의 시간은 두 가지 방식 모두 겹치는 시간입니다.

여기서 e1을 선택하는 경우, e2를 선택하는 것보다 e2-e1 만큼의 시간이 더 있습니다.

위 그림에는 없지만 그 시간에 포함되는 회의가 존재할지도 모르죠.

결국 e1을 선택하는 방식은 반드시 e2를 선택하는 방식보다 반드시 회의실 수가 같거나 큰 값을 가질 수 밖에 없습니다. 

 

다시 말해, 가능한 시간에서 가장 빨리 끝나는 회의를 선택하는게 그보다 늦게 끝나는 회의를 선택하는 것보다 항상 선택가능한 회의 수가 크거나 같다. 라고 할 수 있습니다. 

---

개인적으로 이 문제에 대해서는 약간 불만이 있습니다.

답을 얻기 위해서는 회의 시작 시간을 포함해 이중 정렬을 해야 합니다.

왜냐하면 회의를 하는 것도 아니고 안하는 것도 아닌 3 3, 2 2 와 같은 입력들 때문입니다.

글쎄... 이 문제를 정렬 카테고리에 넣기 위해서는 뭐 나쁘지 않은 선택이지만  그럴 경우 이런 크기를 가지지 않는

경계값에 대해 언급이 있어야 하지 않았나 라는 생각이 드네요. 

 

---

아래는 코드 입니다.

 

package backjoon.greedy;

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static Period[] periods;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		periods = new Period[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			periods[i] = new Period(start, end);
		}
		Comparator<Period> comparatorEnd = Comparator.comparingLong(p1 -> p1.end);
		Comparator<Period> comparatorStart = Comparator.comparingLong(p1 -> p1.start);
		Arrays.sort(periods, comparatorEnd.thenComparing(comparatorStart));
//		System.out.println(Arrays.toString(periods));
		int ret = solve();
		System.out.println(ret);
	}

	private static int solve() {
		long lastEnd=0;
		int cnt = 0;
		for (int i = 0; i < periods.length; i++) {
			if(periods[i].start >= lastEnd) {
				cnt ++;
				lastEnd = periods[i].end;
			}
		}

		return cnt;
	}
}
class Period {
	long start, end;
	public Period(long start, long end) {
		this.start = start;
		this.end = end;
	}

	@Override
	public String toString() {
		return "start=" + start +
				", end=" + end +
				'}';
	}

}


class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
}