백준 1931번: 회의실 배정 (Python)

접근

그리디 알고리즘을 이용하여 푸는 문제이다. 회의 시간을 입력받고 이를 다음의 기준에 따라 정렬한 후 탐색을 시작한다.

1. 회의가 끝나는 시간을 오름차순으로 정렬
2. 회의가 동시에 끝날 경우, 같이 끝나는 회의들끼리 회의가 시작하는 시간을 오름차순으로 정렬

이러한 기준으로 정렬했을 경우 다음과 같이 풀 수 있다.

예를 들어 첫번째 회의를 선택하고, 그 회의가 끝나는 시간을 저장한다. 다음 회의들을 탐색하면서 처음으로 시작시간이 이전 회의가 끝나는 시간보다 같거나 커지는 경우를 선택할 경우, 선택된 회의는 기존 회의가 끝난 이후 가장 먼저 시작해서 가장 끝나는 시간이 빠른 회의이다.(회의가 끝나는 시간을 오름차순으로 정렬했기 때문에)

이러한 방식으로 선택하여 가장 많은 회의를 할 수 있는 횟수를 계산할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
s = []
for _ in range(n):
    start, end = map(int, sys.stdin.readline().split())
    s.append([start, end])
s.sort(key=lambda x: (x[1], x[0]))

cnt = 1
end_time = s[0][1]
for i in range(1, n):
    if s[i][0] >= end_time:
        cnt += 1
        end_time = s[i][1]
print(cnt)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!