[python] 1931번 - 회의실 배정

문제

파이썬 풀이

최대 회의 수를 구하기 위해서는 회의시간이 짧은 즉 가장 빨리 끝나는 회의를 배정하면 된다. 계속해서 짧은 회의를 배정하여 사용할 수 있는 회의의 수를 늘리는 것이다.

따라서 회의가 끝나는 시간을 기준으로 살펴본다.

회의가 끝나는 시간이 현재 시간과 가장 가까운 회의를 배정하면된다.

import sys
input = sys.stdin.readline

N = int(input().rstrip())
time_list = []
for i in range(N) :
  time_list.append(list(map(int, input().rstrip().split())))

time_list.sort(key=lambda x: (x[1], x[0]))
count = 0
last_time = 0

for start, end in time_list :
  if last_time <= start :
    count +=1
    last_time = end

print(count)

입력받은 회의시간을 정렬해준다. 이때 정렬 기준은 끝나는 시간을 기준으로 하되 끝나는 시간이 같을 경우 두 번째 정렬 기준을 시작 시간으로 해주었다.

이미 가장 빨리 끝나는 시간 순으로 정렬을 해두었기 때문에 반복문을 돌면서 만나는 회의시간은 가장 최선의 시간이다.

따라서 현재 시간보다 시작 시간이 빠르지만 않으면 회의실을 배정할 수 있다.

last_time에 이 전의 회의가 끝난 시간을 기록해두어 현재 시간 역할을 해준다.