[정글 베이직29]그리디 - 회의실 배정

종료 시간이 가장 빠른 회의부터 고르면 최대한 많은 회의를 배정할 수 있는 대표 그리디 문제

문제 한눈에 보기

입력	회의 목록 [(시작, 종료), ...]
목표	겹치지 않게 최대한 많은 회의를 선택하기
핵심 전략	종료 시간이 가장 빠른 회의부터 선택
예시	선택 예: [(1,4), (5,7), (8,11), (12,14)]

핵심 1

빨리 끝나는 회의를 먼저 고르면 뒤에 더 많은 회의를 넣을 여지가 생긴다.

핵심 2

이미 선택한 마지막 회의의 종료 시간 last_end 만 추적하면 된다.

핵심 3

새 회의 시작 시간이 last_end 이상이면 선택 가능하다.

왜 종료 시간 기준 정렬일까?

회의를 최대한 많이 배정하려면, 회의실을 빨리 비워 주는 선택이 유리하다. 그래서 시작 시간이 아니라 종료 시간이 빠른 회의를 우선 선택한다.

그리디의 핵심은 매 순간 가장 유리한 선택을 하는 것이고, 이 문제에서는 그 선택이 바로 빨리 끝나는 회의다.

최종 코드

def select_meetings(meetings):
    if meetings == []:
        return 0, []

    meetings.sort(key=lambda x: (x[1], x[0]))
    selected = [meetings[0]]
    last_end = meetings[0][1]

    for i in range(1, len(meetings)):
        if meetings[i][0] >= last_end:
            selected.append(meetings[i])
            last_end = meetings[i][1]

    return len(selected), selected

한 줄씩 설명

줄	코드	설명
1-2	if meetings == []: return 0, []	회의가 없으면 선택할 것도 없으므로 0개와 빈 리스트 반환.
4	meetings.sort(key=lambda x: (x[1], x[0]))	종료 시간 기준으로 정렬한다. 종료 시간이 같으면 시작 시간이 빠른 순으로 보조 정렬하면 더 안정적이다.
5	selected = [meetings[0]]	가장 먼저 끝나는 회의를 우선 선택한다.
6	last_end = meetings[0][1]	현재 마지막으로 선택한 회의의 종료 시간을 기록한다.
8	for i in range(1, len(meetings)):	나머지 회의들을 차례대로 검사한다.
9	if meetings[i][0] >= last_end:	새 회의 시작 시간이 이전 회의 종료 시간 이상이면 겹치지 않는다.
10-11	selected.append(meetings[i]) last_end = meetings[i][1]	선택 목록에 넣고, 마지막 종료 시간을 새 회의 종료 시간으로 갱신한다.
13	return len(selected), selected	선택된 회의 개수와 실제 목록을 반환한다.

예시 시뮬레이션

입력:

[(1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11), (8,12), (2,13), (12,14)]

1. (1, 4) 선택

2. (5, 7) 선택

3. (8, 11) 선택

4. (12, 14) 선택

총 4개 회의를 배정할 수 있다.

자주 하는 실수

• 시작 시간 기준으로 정렬하면 최대 개수를 보장하지 못한다.
• 회의를 선택한 뒤 last_end 갱신을 빼먹으면 다음 비교가 전부 꼬인다.
• 종료 시간이 같은 회의가 있을 때는 (종료, 시작) 정렬이 더 안전하다.

시간복잡도

정렬이 필요하므로 O(n log n)

공간복잡도

선택된 회의 저장으로 O(n)

한 문장 정리

회의실 배정은 종료 시간이 가장 빠른 회의를 먼저 고르는 그리디 전략이 정답이 되는 대표 문제다.