BOJ 1931 회의실 배정 python

기

이 문제를 어떻게 풀어야 할 지 생각하다가, 회의가 시작하는 시간이나 회의의 길이도 중요하지만 끝나는 시간이 더 중요하다는 사실을 깨달았다.

예를 들어 다음과 같은 경우를 생각해보자.

1 4 라는 입력의 경우, 2 3이나 3 3보다 회의 길이가 길지만 빨리 끝마치므로, 이후에 더 많은 다른 회의가 시작될 수 있다. 반면에 회의 길이가 아무리 짧아도 마치는 시간이 늦으면 회의실을 배정받을 수 없다.

승

그래서 회의가 마치는 시간을 기준으로 정렬하기로 했다. 정렬을 하고 나서 확인했더니 테스트케이스와 순서가 똑같았다. 이 문제에서는 의도적으로 마치는 시간을 기준으로 정렬된 회의 시간을 제공한 것이다.

전

시작 시간과 관계 없이 가장 먼저 마치는 회의가 맨 앞에 오게 되고, 이 회의를 배정표에 집어넣었다. 이후 반복문을 돌면서 시작 시간이 현재 배정표의 마지막 종료 시간과 같거나 더 늦는 강의를 선택하는 방식으로 배정표를 완성할 수 있었다.

종료 시간을 기준으로 먼저 정렬을 했기 때문에, 일찍 시작해서 늦게 마치는 회의는 이미 리스트의 뒤쪽에 있으며, 앞 순위에 있다고 하면 어차피 그 시간에 겹치는 회의가 많이 없기 때문에 이 풀이가 적용될 수 있었다.

결

이 문제는 현재에서 가장 최선의 선택을 함으로써 최적해를 도출하는 그리디 문제이다. 그리디 문제에서 최적의 선택을 하기 위해서는 정렬을 잘 이용하면 좋다는 정보를 얻었다.

참고) 시작시간으로 먼저 오름차순 정리를 한 다음 종료시간으로 오름차순 정리를 해야 한다!

---

코드

import sys
n = int(input())
l = []
for _ in range(n):
    s,e = map(int, sys.stdin.readline().strip().split())
    l.append((s,e))

l = sorted(l, key = lambda x: x[0])
l = sorted(l, key = lambda x: x[1])

start = l[0][0]
end = l[0][1]
cnt = 1

for s,e in l[1:]:
    if s >= end:
        start,end = s,e
        cnt += 1

print(cnt)