Yunsu's Log

BOJ 1931: 회의실 배정

8 min read

Note

그리디 알고리즘(Greedy Algorithm)을 활용하여 최대한 많은 회의를 선택하는 문제입니다.

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

문제 링크: https://www.acmicpc.net/problem/1931

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제

예제 입력 1:

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1:

4

힌트: (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

문제 분석

이 문제는 그리디 알고리즘을 사용하는 전형적인 문제입니다.

핵심 포인트

  1. 회의 선택: 겹치지 않는 회의를 최대한 많이 선택
  2. 그리디 전략: 종료 시간이 가장 빠른 회의부터 선택
  3. 정렬 기준: 종료 시간 기준 정렬 (같으면 시작 시간 기준)

왜 종료 시간 기준인가?

종료 시간이 빠른 회의를 선택하면:

  • 더 많은 회의를 선택할 수 있는 기회가 생김
  • 남은 시간이 최대화됨

해결 방법

그리디 알고리즘을 사용합니다:

  1. 회의를 종료 시간 기준으로 정렬 (같으면 시작 시간 기준)
  2. 첫 번째 회의를 선택
  3. 다음 회의 중 시작 시간이 이전 회의 종료 시간 이상인 것을 선택
  4. 반복

코드 구현

제공된 코드

import sys
 
readline = sys.stdin.readline
 
n = int(readline())
 
schedules: list[(int, int)] = []
 
for _ in range(n):
    start, end = map(int, readline().rstrip().split())
    schedules.append((start, end))
 
schedules.sort(key=lambda x: (x[1], x[0]))
 
result = 0
time = 0
 
for i in range(n):
    # 시작시간이 현재 시간보다 늦으면 +1
    if time <= schedules[i][0]:
        result += 1
        time = schedules[i][1]
 
print(result)

코드 분석

1. 입력 처리

import sys
 
readline = sys.stdin.readline
 
n = int(readline())
 
schedules: list[(int, int)] = []
 
for _ in range(n):
    start, end = map(int, readline().rstrip().split())
    schedules.append((start, end))
  • 입력 최적화를 위해 sys.stdin.readline() 사용
  • 회의의 시작 시간과 종료 시간을 리스트에 저장

2. 정렬

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

정렬 기준:

  • 첫 번째: 종료 시간 (x[1]) - 오름차순
  • 두 번째: 시작 시간 (x[0]) - 오름차순

이유:

  • 종료 시간이 빠른 회의를 우선 선택
  • 종료 시간이 같으면 시작 시간이 빠른 것을 선택

3. 그리디 선택

result = 0
time = 0
 
for i in range(n):
    # 시작시간이 현재 시간보다 늦으면 +1
    if time <= schedules[i][0]:
        result += 1
        time = schedules[i][1]

동작 과정:

  1. time: 마지막으로 선택한 회의의 종료 시간
  2. 현재 회의의 시작 시간이 time 이상이면 선택 가능
  3. 선택하면 result 증가, time 업데이트

개선된 코드

더 명확하게 작성한다면:

import sys
 
readline = sys.stdin.readline
 
n = int(readline())
meetings = []
 
for _ in range(n):
    start, end = map(int, readline().rstrip().split())
    meetings.append((start, end))
 
# 종료 시간 기준 정렬 (같으면 시작 시간 기준)
meetings.sort(key=lambda x: (x[1], x[0]))
 
count = 0
last_end = 0
 
for start, end in meetings:
    if start >= last_end:
        count += 1
        last_end = end
 
print(count)

개선 사항:

  • 변수명을 더 명확하게 (schedules → meetings, time → last_end)
  • 튜플 언패킹 사용 (start, end)

시간 및 공간 복잡도

시간 복잡도

  • 정렬: O(n log n) - 회의 개수만큼
  • 그리디 선택: O(n) - 한 번 순회
  • 전체: O(n log n)

공간 복잡도

  • 회의 리스트: O(n)
  • 전체: O(n)

예제 동작 과정

예제 입력 1: n=11

정렬 전:

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

정렬 후:

[(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) 선택 → last_end = 4, count = 1
  2. (3, 5) 스킵 (시작 시간 3 < 4)
  3. (0, 6) 스킵 (시작 시간 0 < 4)
  4. (5, 7) 선택 → last_end = 7, count = 2
  5. (3, 8) 스킵 (시작 시간 3 < 7)
  6. (5, 9) 스킵 (시작 시간 5 < 7)
  7. (6, 10) 스킵 (시작 시간 6 < 7)
  8. (8, 11) 선택 → last_end = 11, count = 3
  9. (8, 12) 스킵 (시작 시간 8 < 11)
  10. (2, 13) 스킵 (시작 시간 2 < 11)
  11. (12, 14) 선택 → last_end = 14, count = 4

결과: 4개

그리디 알고리즘의 정당성

왜 이 방법이 최적해인가?

증명:

  1. 종료 시간이 가장 빠른 회의를 선택하지 않는다고 가정
  2. 다른 회의를 선택하면, 그 회의의 종료 시간이 더 늦음
  3. 따라서 더 적은 회의를 선택할 수 있음
  4. 따라서 종료 시간이 가장 빠른 회의를 선택하는 것이 최적

주의사항

1. 정렬 기준

정렬 기준이 매우 중요합니다:

  • 종료 시간 기준 정렬이 핵심
  • 종료 시간이 같으면 시작 시간 기준 정렬

2. 경계 조건

회의의 시작 시간과 종료 시간이 같을 수 있습니다:

  • start >= last_end 조건으로 처리 가능

3. 입력 최적화

N이 최대 100,000이므로 input() 대신 sys.stdin.readline()을 사용해야 합니다.

관련 알고리즘

그래프 뷰

백링크