[백준] 1931번 회의실 배정 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

나의 풀이

n = int(input())
schedule = []
for _ in range(n):
  schedule.append(list(map(int, input().split())))

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

ans = 1
end_time = schedule[0][1]

for i in range(1, n):
  if end_time <= schedule[i][0]:
    end_time = schedule[i][1]
    ans += 1

print(ans)

 

접근법 및 코드 설명

처음에는 브루트포스 문제 마냥 이중 for문을 이용해 접근하였으나, 시간초과 판정을 받았다.

 

애초부터 회의 정보들을 전처리 해주고 와야겠다는 생각에 정렬 방식을 생각해냈다.

 

가장 중요한 건 회의 정보들에 대해서 시작시각을 기준으로 한 번, 그리고 종료시각을 기준으로 다시 한 번 정렬해주는 것이다.

 

for문을 돌면서 현재 회의 종료시각이 다음 원소의 회의 시작시각보다 작다면, 회의실을 새로 배정한다는 의미에서 ans에 1을 추가한 후, 회의 종료시각을 새로운 회의 배정시각의 종료시각으로 업데이트 해준다.

 

그렇게 for문이 종료되고 ans에 담긴 값이 회의실을 최대로 사용할 수 있는 회의 수이다.