[Greedy] 백준 1931번 “회의실 배정” Python 풀이

문제 링크

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

풀이

• 주어진 시작 시간과 종료 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는, 회의가 빨리 끝나는 순서대로 정렬을 진행해야 한다.
  • 회의가 빨리 끝날수록 뒤에서 고려할 수 있는 회의가 많기 때문이다.
  • 만약, 회의가 빨리 시작하는 순서대로 정렬을 진행한다면, 오히려 회의가 늦게 끝날 수도 있다.
• 또한, 회의가 끝나는 시간이 같을 경우엔, 회의가 빨리 시작하는 순서대로 정렬을 진행해야한다.
  • 예를 들어, 회의가 (2, 2), (1, 2) 순서대로 주어진다면, (2, 2) 회의만 진행할 수 있지만
  • (1, 2), (2, 2) 순서대로 주어진다면, (1, 2), (2, 2) 회의를 모두 진행할 수 있기 때문이다.
• 따라서, 주어진 회의 시간들을, 회의 종료 시간 기준 오름차순 정렬, 회의 시간 시간 기준 오름차순 정렬하면 된다.
• 이후, 정렬된 회의 시간들을 탐색하며, 다음 회의 시작 시간이 이전 회의 종료 시간보다 크거나 같다면,
• 이전 회의 종료 시간을 업데이트하고, 최대 회의 개수를 증가시키면 된다.
• 알고리즘의 세부 설명은 아래 코드와 같다.

코드

import sys

# 회의의 수
n = int(sys.stdin.readline())

# 회의 시간
meeting_times = []

# 회의의 시작 시간과 끝나는 시간
for _ in range(n):
    start, end = map(int, sys.stdin.readline().split())
    meeting_times.append((start, end))

# 회의 시간을 종료 시간 기준 및 시작 시간 기준으로 정렬
meeting_times = sorted(meeting_times, key = lambda x : (x[1], x[0]))

# 최대 회의 개수
count = 1
# 이전 회의 종료 시간
end_time = meeting_times[0][1]

for i in range(1, n):
    # 다음 회의 시작 시간이 이전 회의 종료 시간보다 크거나 같다면
    if (meeting_times[i][0] >= end_time):
        # 이전 회의 종료 시간 업데이트
        end_time = meeting_times[i][1]
        # 최대 회의 개수 증가
        count += 1

print(count)