Greedy Proof

그리디 증명은 첫 선택을 교환해 닫는다

가장 빨리 끝나는 회의를 먼저 골라도 최적해가 줄지 않는다는 것을 시간축에서 확인한다.

그리디 선택 남은 공간 교환 대상 막힌 후보
시간 123456789
G
A 1-3
O
B 1-5
후보
겹침
C 5-7
D 7-9
1. 첫 선택 비교

그리디가 고른 A는 최적해의 첫 회의 B보다 늦게 끝나지 않는다.

2. 교환

B를 A로 바꿔도 이후에 선택할 수 있는 시간 구간은 줄어들지 않는다.

3. 부분 문제 유지

A 뒤에 남은 후보는 같은 활동 선택 문제이므로 같은 규칙을 반복한다.

증명 질문 이 예시의 답 빠지면 안 되는 이유
선택 규칙 끝나는 시간이 가장 빠른 회의를 고른다. 규칙이 모호하면 교환 대상이 정해지지 않는다.
교환 논증 더 늦게 끝나는 첫 회의를 A로 바꿔도 남은 공간이 작아지지 않는다. 현재 선택이 최적해와 양립하는지 증명하지 못한다.
반례 탐색 가장 짧은 회의, 가장 빨리 시작하는 회의는 같은 논증이 닫히지 않는다. 그리디가 아니라 휴리스틱이 된다.