[알고리즘] 회의실 배정 (그리디 기법)

문제 설명

한 개의 회의실을 여러 회의들이 겹치지 않게 사용하려고 할 때, 사용할 수 있는 회의의 최대 개수를 구하는 문제입니다.

• 조건: 회의는 중단될 수 없으며, 끝나는 동시에 다음 회의를 시작할 수 있습니다. 시작 시간과 종료 시간이 같을 수도 있습니다.

핵심 풀이 전략: Greedy (탐욕법)

이 문제의 핵심은 “어떤 회의를 먼저 선택해야 뒤에 더 많은 회의를 넣을 수 있는가?”입니다.

1. 상식적인 접근: 빨리 끝나는 회의를 먼저 선택할수록 뒤에 남는 시간이 많아집니다. 따라서 종료 시간을 기준으로 오름차순 정렬하는 것이 핵심입니다.

2. 동작 원리:
   • 종료 시간이 가장 빠른 회의를 먼저 선택합니다.
   • 그 회의가 끝난 직후(혹은 그 이후)에 시작할 수 있는 회의 중 가장 빨리 끝나는 것을 반복적으로 선택합니다.
3. 정렬 기준:
   • 1차 기준: 종료 시간 오름차순
   • 2차 기준 (종료 시간이 같을 때): 시작 시간 오름차순 (시작하자마자 끝나는 회의들을 누락 없이 처리하기 위함)

---

종료 시간을 기준으로 정렬한 뒤, 이전 회의의 종료 시간보다 현재 회의의 시작 시간이 크거나 같으면 선택하는 방식으로 구현하면 O(N log N)의 시간 복잡도로 정답을 얻을 수 있습니다.