[Python/파이썬] 백준 1931 - 회의실 배정

문제 설명

 

입출력 예제

 

---

풀이 코드

가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다.

앞의 일이 종료되어야 뒤의 일도 진행할 수 있는 것과 마찬가지로 회의가 빨리 끝날수록 뒤에서 더 많은 회의가 가능하다.

 

정렬을 하는데 끝나는 시간이 오름차순으로 정렬되었을 경우 시작시간은 같지만 끝나는 시간이 같은 회의가 생길 수가 있다.

이 경우를 대비하여 첫 번째로 끝나는 시간 기준 오름차순, 두 번째로 시작하는 시간 기준 오름차순 으로 총 2번의 정렬이 필요하다.

 

위의 정렬을 해주기 위해서는 위 순서대로 sort를 하는것이 아니라 반대로 해야한다.

즉, 시작시간의 오름차순으로 정렬을 한 뒤, 정렬된 리스트를 다시 끝나는 시간으로 오름차순 정렬해주는 것이다.

 

이미 시작시간이 오름차순으로 정렬된 상태이기 때문에 끝나는 시간으로 오름차순 정렬을 또 적용해도 끝나는 시간이 같을 때에는 시작시간의 오름차순으로 정렬이 되어있다.

 

* 위 예제를 위의 설명 처럼 정렬하면 다음과 같이 나온다.

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())

time = []

for _ in range(n):
  start, end = map(int, input().split())
  time.append([start, end])

time = sorted(time, key=lambda a: a[0]) # 시작 시간을 기준으로 오름차순
time = sorted(time, key=lambda a: a[1]) # 끝나는 시간을 기준으로 다시 오름차순

last = 0 # 회의의 마지막 시간
conut = 0 # 회의 개수

for i, j in time:
  if i >= last: # 시작시간이 회의의 마지막 시간보다 크거나 같을경우
    conut += 1
    last = j

print(conut)