활동선택 알고리즘

활동선택 문제

(1,4),(3,5),(1,6) ... (12,14)

회의 종료시간이 가장 빠른 회의를 먼저 선택하면 된다.

종료시간을 기준으로 회의들을 오름차순 정렬한다.

종료시간이 가장 빠른 회의를 찾자마자 확정 (1,4)

⇒ 이제 4시 이후로 부터 회의가 가능하다.

4시 이후에 가장 빨리 끝나는 회의 찾기 (5,7)

⇒ 이제 7시 이후로 회의가 가능

7 시 이후로 가장 빨리 끝나는 회의 찾기 (8,11)

⇒ 이제 11시 이후로 회의가능

11시 이후로 가장 빨리 끝나는 회의 (12,14)

⇒ 정답은 4회

문제 전략

1. 끝나는 시간을 기준으로 오름차순 정렬
2. 빠르게 끝나는 회의를 선택하여 확정한다.
3. 이후로 가능한 회의 중, 빠르게 끝나는 회의를 선택하여 확정한다.