implementation guard
선택 규칙은 타임라인에서 먼저 검증한다
그리디 구현 전에는 정렬 키, 선택, 폐기, 남은 문제를 같은 예시 위에서 확인해야 한다.
선택
겹쳐서 폐기
다음 후보
회의 선택 예시: 종료 시간이 빠른 순서
시간
1
2
3
4
5
6
7
8
9
A
B
C
D
E
| 점검 항목 | 이 예시에서 보이는 증거 | 실패 신호 |
|---|---|---|
| 정렬 키 | 종료 시간이 빠른 A를 먼저 고르면 남는 시간이 가장 넓다. | 시작 시간, 길이 기준이 작은 반례에서 깨짐 |
| 폐기 근거 | B와 C는 A와 겹치므로 최적 후보에서 안전하게 제거된다. | 겹치지 않는 후보까지 함께 버림 |
| 남은 문제 | A 뒤에는 D, E를 고르는 같은 형태의 문제가 남는다. | 첫 선택 뒤 문제 구조가 달라짐 |