[Python] 백준 #1931 - 회의실 배정

문제

---

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

1931번: 회의실 배정

 

 

풀이

---

import sys
input = sys.stdin.readline

n = int(input())
t = []
for _ in range(n):
    a,b = map(int,input().split())
    t.append([a,b])
end,cnt=0,0
for a,b in sorted(t,key=lambda x:(x[1],x[0])): # 회의의 끝나는 시간, 시작시간을 오름차순으로 정렬
    if end <= a: # 그 전의 회의의 끝나는 시간보다 현재 회의의 시작시간이 더 크다면 
        cnt+=1 # 회의 개수 +1
        end = b # 회의 마치는 시간 넣어줌
print(cnt)

 

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아야한다.

 

 

회의의 개수를 찾기 위해서는 현재 회의가 끝난 시간보다 다음 회의의 시작 시간이 더 큰 개수를 찾으면된다.

 

 

최대한 많은 회의를 잡기 위해서는 회의가 빨리 끝나는 순대로 찾으면된다. 즉, 회의의 끝나는 시간이 빠른 순서대로 정렬하면 된다.

ex) [[3, 8],[1, 3],[0, 6]]

정렬하기 전 -  [3,8]의 회의만 진행할 수 있어 1번의 회의만 가능하다.

정렬한 후 -  [[1, 3],[0, 6],[3, 8]]가 되어 [1,3],[3,8]의 회의 , 총 2개의 회의가 가능하다.

 

 

정렬 후 끝나는 시간이 같을 수 있는 조건도 생각해야한다. 이때는 회의의 시작시간순으로 정렬해야한다.

ex) [[4,4],[3,4]]

정렬하기 전 -  [4,4]의 회의만 진행할 수 있어 1번의 회의만 가능하다.

정렬한 후 -  [3,4],[4,4] , 최대 2번의 회의가 가능하다.