[Python] Baekjoon - 1931. 회의실 배정

백준 1931번 회의실 배정 문제를 파이썬을 이용해 풀어보았다. 그리디 알고리즘을 이용한 가장 기본적인 문제이며 정렬도 이용해야 한다. 문제는 N개의 회의가 1개의 회의실을 사용하려고 할 때, 진행할 수 있는 회의의 최대 개수를 구하는 문제다.

 

1931번 회의실 배정 문제 정보

알고리즘 분류

- 그리디 알고리즘 및 정렬

난이도

- 실버 2

 

회의실 배정 문제 요약

1개의 회의실을 예약한 N개의 회의 스케줄이 주어졌을 때, 진행할 수 있는 회의의 최대 개수를 구하는 문제다.

 

문제 풀이 과정

가장 기본적인 그리디 알고리즘 문제이다. 전체 회의 스케줄을 끝나는 시간이 이른 회의 순으로, 끝나는 시간이 같다면 시작 시간이 이른 순으로 정렬한다. 끝나는 시간이 이른 회의 먼저 회의 가능 여부를 판단하고 회의가 가능하다면 카운트를 증가시킨다.

 

코드

import sys

N = int(input())
schedule = []
for _ in range(N):
    s, d = map(int, sys.stdin.readline().split())
    schedule.append((d, s))

schedule.sort()
end_time = 0
meeting_cnt = 0

for d, s in schedule:
    if s >= end_time:
        end_time = d
        meeting_cnt += 1

print(meeting_cnt)