greedy rule

규칙은 “버린 후보”를 설명할 때만 채택한다

그리디 선택 규칙은 직감이 아니라, 지금 고른 뒤 탈락한 후보가 왜 답이 아닌지 설명해야 한다.

채택 검토 반례 동점 규칙

활동 선택에서 후보 규칙 세 가지를 비교한다

가장 빨리 끝남 채택
회의
A
B
C
D
E
끝
3
5
6
7
9

첫 회의를 A로 교환해도 뒤쪽 선택 공간이 줄지 않는다.

가장 짧은 구간 반례
회의
A
B
C
D
E
길이
2
1
2
2
3

짧은 회의가 중간을 차지하면 양쪽 후보를 동시에 막을 수 있다.

가장 빨리 시작 폐기
회의
A
B
C
D
E
끝
8
3
5
7
9

빨리 시작해도 오래 붙잡으면 이후 회의를 대부분 잃는다.

판정 질문 통과 기준 실패 신호
무엇을 버리나 현재 선택과 겹치는 후보가 왜 대체 가능한지 설명한다. “좋아 보인다”는 직감만 남는다.
교환이 닫히나 최적해의 첫 선택을 현재 선택으로 바꿔도 손해가 없다. 반례 하나로 전체 규칙이 깨진다.
남은 문제가 같나 선택 뒤 남은 후보에도 같은 규칙을 반복할 수 있다. 한 번 선택 후 조건이 달라진다.
핵심: 그리디 규칙은 “왜 지금 버린 후보가 답이 될 수 없는가”를 설명할 때만 구현으로 옮긴다.