[정글 알고리즘] - [중] 백준1931- 회의실 배정- 골드5

 

정렬 뒤 어떤 회의가 선택되고 왜 탈락하는지 흐름 중심으로 정리한 상세형 버전이다.

1. 문제를 아주 짧게 말하면

회의가 서로 겹치지 않게 하면서 최대 몇 개를 선택할 수 있는지 구하는 대표적인 그리디 문제다. 끝나는 시간이 빠른 회의를 먼저 잡는 것이 핵심이다. [Source](https://www.acmicpc.net/problem/1931)

2. 핵심 아이디어

왜 종료 시간이 빠른 회의를 먼저 고를까?

가장 빨리 끝나는 회의를 먼저 골라야 이후에 더 많은 회의를 붙일 여지가 남기 때문이다.

정렬 기준: 종료 시간 오름차순 → 종료 시간이 같으면 시작 시간 오름차순

3. 전체 코드

1import sys

2

3input = sys.stdin.readline

4n = int(input())

5meetings = [tuple(map(int, input().split())) for _ in range(n)]

6

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

8

9count = 0

10last_end = 0

11

12for start, end in meetings:

13 if start >= last_end:

14 count += 1

15 last_end = end

16

17print(count)

4. 코드 한 줄씩 설명

줄	코드	설명
3	input = sys.stdin.readline	빠른 입력을 위한 설정이다.
4	n = int(input())	회의 개수를 입력받는다.
5	meetings = [tuple(map(int, input().split())) for _ in range(n)]	각 회의의 시작 시간과 종료 시간을 튜플로 저장한다.
7	meetings.sort(key=lambda x: (x[1], x[0]))	끝나는 시간이 빠른 순으로, 같다면 시작 시간이 빠른 순으로 정렬한다.
9	count = 0	선택한 회의 수를 셀 변수다.
10	last_end = 0	마지막으로 선택한 회의의 종료 시간을 저장한다.
12	for start, end in meetings:	정렬된 회의를 앞에서부터 하나씩 확인한다.
13	if start >= last_end:	현재 회의 시작 시간이 마지막 종료 시간 이상이면 겹치지 않는다.
14	count += 1	회의를 선택했으므로 개수를 1 늘린다.
15	last_end = end	이 회의의 종료 시간을 새로운 기준으로 갱신한다.
17	print(count)	최대로 선택한 회의 개수를 출력한다.

5. 회의 선택 과정 시각화

문제 예시 회의들을 종료 시간 기준으로 정렬한 뒤 순서대로 보면 다음처럼 선택/탈락이 갈린다.

회의 (1, 4)

시작 1 >= 마지막 종료 0 이므로 선택

회의 (3, 5)

시작 3 < 마지막 종료 4 이므로 겹쳐서 제외

회의 (0, 6)

시작 0 < 마지막 종료 4 이므로 겹쳐서 제외

회의 (5, 7)

시작 5 >= 마지막 종료 4 이므로 선택

회의 (3, 8)

시작 3 < 마지막 종료 7 이므로 겹쳐서 제외

회의 (5, 9)

시작 5 < 마지막 종료 7 이므로 겹쳐서 제외

회의 (6, 10)

시작 6 < 마지막 종료 7 이므로 겹쳐서 제외

회의 (8, 11)

시작 8 >= 마지막 종료 7 이므로 선택

회의 (8, 12)

시작 8 < 마지막 종료 11 이므로 겹쳐서 제외

회의 (2, 13)

시작 2 < 마지막 종료 11 이므로 겹쳐서 제외

회의 (12, 14)

시작 12 >= 마지막 종료 11 이므로 선택

6. 최종 선택된 회의 흐름

최종적으로 선택되는 대표 경로는 [(1, 4), (5, 7), (8, 11), (12, 14)] 이다.

(1, 4)

 

(5, 7)

 

(8, 11)

 

(12, 14)

 

7. 자주 헷갈리는 포인트

• start > last_end 가 아니라 start >= last_end 다. 끝나는 즉시 바로 다음 회의를 시작할 수 있다.
• 시작 시간이 아니라 종료 시간 기준으로 정렬해야 한다.
• 종료 시간이 같을 때의 보조 정렬을 같이 두는 편이 안전하다.

8. 복잡도

정렬이 핵심이라 시간 복잡도는 O(N log N) 이다.

이후 순회는 O(N) 이다.

원문 문제 링크

https://www.acmicpc.net/problem/1931