회의실 배정_그리디 기법 활용
문제 포인트
- 회의는 시작 시간과 종료 시간이 존재하며, 회의가 겹치는 회의는 동시에 열릴 수 없음
- 하나의 회의실을 공통으로 사용하고, 이를 예약하는 개념으로 생각
- 가능한 많은 회의가 열리기 위해서 회의를 어떻게 배정해야 할 지에 대해 생각하는 문제
활동 선택 문제_일반화
- 시작 시간과 종료 시간이 있는 n개의 활동들의 집합에서 서로 겹치지 않는 최대 갯수의 활동들의 집합 S를 구하는 문제
- 양립 가능한 활동들의 크기가 최대가 되는 S의 부분집합을 선택하는 문제
해결 포인트
- 종료 시간 순으로 활동들을 정렬한다.
- 종료 시간이 같다면, 시작 시간이 빠르던 늦던 혹은 회의 시간이 짧던 길던 하나의 회의밖에 올 수 없는 점이 중요한 포인트이다.
- 다른 포인트
- 빨리 시작하는 순으로 정렬 : 시작 시간이 빠르더라도 종료 시간이 긴 회의가 있으면 최대 갯수가 될 수 없음
- 회의 시간이 짧은 순으로 정렬 : 시작 및 종료 시간이 중간에 어중간하게 있는 경우 확인할 게 많아짐
- 한 회의를 뽑고, 그 다음 회의를 뽑을 때에는 그 전에 뽑은 회의와 겹치는지만 확인하면 된다.
- 모든 경우를 확인하지 않아도 되고, 단 하나의 회의 시간(이전에 선택된 회의 시간)만 확인하면 되기 때문에 속도면에서 매우 유리하다.
- 보통 nlogN으로 취급(정렬이 nlogN인데, 정렬이 거의 전부인 느낌으로 취급)
수도 코드
// 시작 시간과 종료 시간이 있는 커스텀 클래스 작성
// 해당 커스텀 클래스가 종료 시점으로 오름차순으로 정렬할 수 있도록 comparable 혹은 comparator 설정
// 종료 시간이 같은 경우, 문제에 따라서 시작 시간 정렬도 필요할 수 있으니 확인할 것(예를 들면 시작하자마자 종료되는 회의가 있는 경우)
// 회의 커스텀 클래스를 참조형으로 하는 배열을 선언하고 입력받기
// 입력받은 배열을 sort
// 첫 회의는 저장하고 시작
// 2번쨰 회의부터 순회하며 양립할 수 있는지 조건을 확인 및 가능하다면 결과 리스트에 저장