[BOJ][python] 1931 회의실 배정

lambda key를 이용한 sort  

 

문제

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

나의 풀이

끝나는 시간과 시작하는 시간을 차례로 정렬한 후 가능한 예약시간이 등장할 때마다 카운트를 늘려주는 식으로 해결할 수 있습니다.

일정이 빠르게 끝날 수록 뒤에 여유 시간이 많아져 추가일정을 더 많이 넣을 수 있습니다.
같은 시간에 끝나는 경우 가능한 일정 중 가장 빨리 시작할 수 있는 일정을 집어 넣어야 합니다. 이렇게 구현해야 동일시간에 시작하고 끝나는 일을 놓치지 않고 처리할 수 있습니다.

사용된 개념 중 참고할 만한 것은 sort의 key로 lambda 함수를 사용했다는 것입니다. 파이썬에서 lambda를 사용하면 다중조건으로 한번에 정렬을 완료할 수 있습니다. 참고 사이트

lambda 식을 사용하는 더 많은 예제는 이곳을 들어가면 보실 수 있습니다.

import sys

read = lambda: sys.stdin.readline().strip()

N = int(read())
time = [[0] * 2 for _ in range(N)]

for i in range(N):
    s, e = map(int, read().split())
    time[i][0] = s
    time[i][1] = e
# 람다식을 이용해 tuple을 생성하고 key로 설정해줍니다. 
time.sort(key=lambda x: (x[1], x[0]))

cnt = 1
last_end_time = time[0][1]
for i in range(1, N):
    if time[i][0] >= last_end_time:
        cnt += 1
        last_end_time = time[i][1]

print(cnt)